Instructor: Dr. Inst. Emre SERMUTLU

Room: R - 201

Office Hours: Monday 11.20-13.10

Course Description: Introduction to strings, languages, and grammars. Concept of abstract machines and language acceptance. Deterministic and nondeterministic finite state machines. Regular expressions. Machines with pushdown tape. Context-free grammars and parse trees. Turing machines and recursive functions. Unrestricted grammars.

Textbook: Michael Sipser,Introduction to the Theory of Computation,  Third International Edition, Cengage, 2013.

Reference Books:  Hopcroft, Motwani, Ullman, Automata Theory, Languages and Computation, 3rd ed., Pearson 2007

Peter Linz, An Introduction to Formal Languages and Automata, 5th ed. Jones Bartlett, 2012

Course Objectives:

• To introduce the formal languages and finite automata.
• To analyze the concepts of determinism and indeterminism.
• Give the students basic understanding of abstraction using formal languages and abstract machines
• Investigate the concept and limits of computation and establish a theoretical foundation for computer science.

Learning Outcomes:

• Understand the functioning of finite-state machines.
• Understand the equivalence of deterministic and nondeterministic automata.
• Understand the equivalence of context-free grammars and pushdown automata.
• Classify formal languages as regular, context-free, Turing decidable, Turing recognizable.
• Analyze theoretical problems in classes P and NP.

Evaluation Criteria:

First Midterm: %30, 

Second Midterm: %30

Final: %40

Attendance: Compulsory

Exam Dates:

First Midterm: 06.11.2019, Wednesday at 17:30. 

Second Midterm: 11.12.2019, Wednesday at 17:30. 

Final: 09.01.2020 at 15:00. 

Make Up: 14.01.2020 at 12:30, L-A14. 

Resit: 29.01.2020 at 10:00, L-111.