**CENG ****491 Formal Languages and Automata**

**Course Syllabus**

**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 |