Information Package
baskent.edu.tr

Program of Computer Engineering (English)

CSE328

AUTOMATA THEORY

Course Code
CSE328
Semester
-
Theory+Practice
3 + 0
ECTS
5
Course TypeElective Course
Course LevelBachelor's Degree
Year of Study-
Semester-
ECTS5
Name of Lecturer(s)
Learning Outcomes

At the end of this course, the students;

  1. Learn basic concepts and models of Automata Theory, Computation and Formal languages.
  2. Be able to solve problems on abstract machines such as Finite state automata, Pushdown automata and Turing machines.
  3. Learn about the representations of formal languages using regular expressions and formal grammars.
  4. Understand abstract models of the computational process and discuss about the limits and power of these models.
Mode of DeliveryFace to face
PrerequisitesNo
Recommended Optional Programme ComponentsNone
Course DescriptionIntroduction to Automata Theory. Basic mathematical concepts and methods. Symbols, Alphabets, Strings, Languages, Problems. Deterministic finite automata. Nondeterministic finite automata. Regular languages and expressions. Kleene's theorem. Formal grammars. Context-free languages. Pushdown automata. Turing machines. Computability and Decidability. Halting problem, Unsolvable problems. Computational complexity: P and NP classes.
Course Contents
WEEK TOPICS
1st Week Introduction to Automata Theory.
2nd Week Basic mathematical concepts and methods.
3rd Week Symbols, Alphabets, Strings, Languages, Problems.
4th Week Deterministic finite automata.
5th Week Nondeterministic finite automata.
6th Week Regular languages and expressions.
7th Week Kleene's theorem.
8th Week Mid-term
9th Week Formal grammars.
10th Week Context-free languages.
11th Week Pushdown automata. Turing machines.
12th Week Computability and Decidability.
13th Week Halting problem, Unsolvable problems.
14th Week Computational complexity: P and NP classes.
15th Week General Review
Recommended or Required Reading1. Hopcroft J.E., Motwani R., Ullman J.D., Introduction to Automata Theory, Languages and Computation, 3/E, Addison Wesley, 2006
2. Kelley D., Automata and Formal Languages, Prentice Hall, 1995
3. Sipser M., Introduction to the Theory of Computation, 2/E, Thomson / Course Technology, 2005
Planned Learning Activities and Teaching Methods
  • Lecture
  • Questions/Answers
  • Presentation
  • Report Preparation
  • Project
  • Experiment
  • Problem Solving
  • Practice
Assessment Methods and Criteria
Quantity Percentage (%)
Mid-term 1 30
Assignment 8 10
Quiz 4 20
Total(%) 60
Contribution of In-term Studies to Overall Grade(%) 60
Contribution of Final Examination to Overall Grade(%) 40
Total(%) 100
Language of InstructionTurkish
Work Placement(s)No

Programme Qualifications / Learning Outcomes

LO1 LO2 LO3 LO4
K1 X X X X
K2
K3
K4
K5
K6
K7
K8 X X
K9
K10
K11