Semester: 2019 - 2020 FALL
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.