Three 50 minutes lectures, per week (3-0-3)
Designation: Elective Course
Course Level: Undergraduate
Prerequisite(s) by Topic:
- DS1. Functions, Relations and Sets
- DS3. Proof Techniques
- DS4. Basics of Counting
Regular Grammars: equivalence of DFA, NDFA and regular expressions, pumping lemma,emptiness and membership. Context-Free Grammars: parsing and ambiguity, normal forms,applications, equivalence of PDA's and CFG's, pumping lemma, emptiness and membership.Turing Machine: programming techniques for Turing machines, equivalence of one-tape and multitape TM's, universal Turing-machine. Undecidability: recursively enumerable and recursive languages, undecidability, problem eduction, undecidable problems of CFG's, RE's and TM's.
P. Linz, An Introduction to Formal Languages and Automata, 4th Edition, Jones and Bartlett Publishers, 2006.
Reference(s) and Other Material:
- J. Hopcroft, R.Motwani and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001.
- Lecture notes on Theory of Computing (handout)
- Design and explain regular languages in different notations: DFA, NFA, regular
- expressions and grammars, and convert between these notations.
- Use the pumping lemma to prove that a given language is not regular.
- Understand pushdown automata, context-free grammars, and their normal forms, and
- apply CYK algorithm on context-free languages.
- Understand the Chomsky hierarchy for language classification, and determine the class of
- a given language and the type of a given grammar.
- Understand the Turing thesis and its implications, and explain basic concepts of the
- theory of decidability.
- Introduction to alphabet, languages, and regular expressions.
- Regular Languages. Finite-state automata, DFA and NFA.
- Equivalence of DFA, NFA and regular expression.
- Pigeon-hole principle, pumping lemma, and non-regular languages.
- Grammar, Context-Free and Context-Sensitive Grammar.
- Context-Free Languages and Pushdown Automata.
- Turing Machines. Recursive and Recursively enumerable languages. Linear
- Bounded automata.
- Hierarchy of Formal Languages and the Chomsky Hierarchy.
- Undecidability, the Halting Problem, Hilbert 10th Problem. Reducibility and
- RiceÃ¢â‚¬â„¢s Theorem.
- GÃƒÂ¶del Incompleteness Theorem and Computational Complexity.