CENG 491 Formal Languages and Automata

Course Syllabus

Instructor: Assist. Prof. Dr. Engin DEMIR Office: L-205 Office Hours: WED 13:30-15:20

Weekly Timetable:

TUE 9:20-11:10 (LB-06) THR 14:20-15:10 (LA-14)

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, Second International Edition, Thomson Course Technology, 2006.

Grading

Midterm Exam 25%
Final Exam 35%
Homeworks 40%

 Course Outline

Weeks Starting Dates Topics Assessments
1 26/09/2016 Finite Automata  
2 03/10/2016 Regular Operations  
3 10/10/2016 Nondeterminism Homework 1
4 17/10/2016 Regular Expressions  
5 24/10/2016 Pumping Lemma  
6 31/10/2016 Context Free Grammars Homework 2
7 07/11/2016 Pushdown Automata  
8 14/11/2016 Non-context-free Languages MIDTERM EXAM
9 21/11/2016 Turing Machines Homework 3
10 28/11/2016 Variants of Turing Machines  
11 05/12/2016 Definition  of Algorithm  
12 12/12/2016 Decidability and Halting Problem Homework 4
13 19/12/2016 P and NP  
14 26/12/2016 NP Completeness  
15 02/01/2017   FINAL EXAM