Engineering / College · Theory of Computation

Theory of Computation Notes – Finite Automata, Regular Expressions, CFG, PDA and Turing Machines with Diagrams

• PDF · 186 KB
• 0 downloads
• English

Theory of Computation notes for third-year B.Tech Computer Science, and useful for GATE CS revision. Covers alphabets and languages, DFA and NFA, regular expressions and the pumping lemma, context-free grammars and normal forms, pushdown automata, Turing machines, decidability and the Chomsky hierarchy, with state diagrams, solved constructions, comparison tables and exam questions. Includes 5 labelled diagrams: The Chomsky hierarchy, from most general to most restricted; A DFA over {0, 1} that accepts strings ending in 1. q1 is the final state; Converting between the forms of regular languages; Parse tree for the string 0011 using S → 0S1 and S → ε; Classes of problems by what a Turing machine can do.