Introduction to computer theory
Automata theory. Background. Languages. Recursive definitions. Regular expressions. Finite automata. Transition graphs. Kleene's theorem. Nondeterminism. Finite automata with output. Regular languages. Nonregular languages. Decidability. Pushdown automata Theory. Context-free grammars. Trees. Regular grammars. Chomsky normal form. Pushdown automata. CFG=PDA. Context-free languages. Non-context-free languages. Intersection and complement. Parsing. Decidability. Turing theory. Turing machines. Post machines. Minsky's theorem. Variations on the TM. Recursively enumerable languages. The encoding of turing machines. The chomsky hierarchy. Computers. Bibliography. Table of theorems.
Number Brief Description Page 1 S S
62 other sections not shown
2PDA A-productions a's and b's accepts all words accepts the language alphabet begin branch called cell CFG's Chapter character circuit Computer Theory concatenation contains context-free languages convert crash derivation tree edge labeled equivalent EXAMPLE Let FA's fc's final finite automaton grammar HALT infinite input letters input string Kleene star language accepted language defined left-most loop mathematical Mealy machine means Moore machine nondeterministic nonterminals number of a's odd number output PALINDROME path PDA's possible problem Prod productions prove Pumping Lemma PUSH read a b READ2 recursive definition regular expression regular languages REJECT replace Rule sequence Show simulate STACK Step string of a's string of terminals substring symbol Tape Head TG that accepts TM Tape TM's transition graph transition table Turing machine words of length write