CENG 491 Formal Languages and Automata

Course Syllabus

Instructor: Assist. Prof. Dr. Engin DEMIR Office: L-215

Office Hours: THU 13:30-15:20

Course Web Site: http://ceng491.cankaya.edu.tr & WebOnline

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.

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.

Textbook

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

Grading

Midterm Exam 25%
Final Exam 35%
Homeworks 40%

 Course Outline

Weeks Topics Assessments
1 Finite Automata  
2 Regular Operations  
3 Nondeterminism Homework 1
4 Regular Expressions  
5 Pumping Lemma  
6 Context Free Grammars Homework 2
7 Pushdown Automata  
8 Non-context-free Languages MIDTERM EXAM
9 Turing Machines Homework 3
10 Variants of Turing Machines  
11 Definition  of Algorithm  
12 Decidability and Halting Problem Homework 4
13 P and NP  
14 NP Completeness  
15   FINAL EXAM