Description |
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 reduction, undecidable problems of CFG's, RE's and TM's.
|