Introduces students to the formal language theory that underlies modern computer science. Topics include different representational forms for regular languages, context-free grammars, pushdown automata, pumping lemmas for regular and context-free languages, and Chomsky's hierarchy.
CSCE 2100 and CSCE 2110
Introduction to Automata Theory, Languages & Computation, Hopcroft, Motwani, Ullman, 3rd edition, Addison Wesley, ISBN 9780321462251
- Convert a regular expression to an equivalent NFA or DFA.
- Apply the pumping lemma for regular languages to prove that a given non-regular language is, in fact not regular.
- Apply the pumping lemma for context-free languages to prove that, given a grammar, G, that is not context-free that G, in fact, is not context-free.
- Prove that any context-free grammar, G, can be converted to a pushdown automata that accepts the same language as G.
- Describe the concept of undecidability, give an example of an undecidable language, UL, and prove that UL is undecidable.
- Demonstrate that a "real" computer can be simulated by a Turing machine.
- Demonstrate the concept of NP-completeness, give an example of an NP-complete problem NPCP, and prove that NPCP is NP-complete.