Theory of Computation

Theory of Computation TOC is an extension of  MCS  , and as such extends on the topics originally covered in MCS, such as: Inductive proofs and definitions (also covered in ICM) Finite automata Kleene's Theorem Non-deterministic finite automata Grammars Regular grammars Context-free grammars Pushdown automata Chomsky hierarchy Level Grammars/Languages Grammar Productions Machines 0 Unrestricted/recursively enumerable α → β [α ∈ ( V  ∪  Σ ) + , β ∈ ( V  ∪  Σ )*] Turing Machine 1 Context-sensitive α → β [α, β ∈ ( V  ∪  Σ ) + , |α| ≤ |β|] Linear-bounded automaton 2 Context-free A → β [A ∈  V , β ∈ ( V  ∪  Σ )*] Pushdown automaton 3 Regular A → a, A → aB, A → Λ [A, B ∈  V , a ∈  Σ ] Finite automaton We could also consider a level 2.5, which is a deterministic context free grammars . Context-Sensitive Languages A grammar is context sensitive if α → β satisfies |α| ≤ |β|, with the possible exception of S → Λ. If S → Λ is present...