Theory of Computation

0 student

Basics:  Sets, Set Operations, Properties of Sets

Automata: Deterministic Finite Automaton (DFA), Non – deterministic Finite Automaton (NFA), Regular languages and regular sets, Equivalence of DFA and NFA. Minimizing the number of states of a DFA. Non-regular languages and Pumping lemma.

PDA: Pushdown Automaton (PDA), Deterministic Pushdown Automaton (DPDA), Non – equivalence of PDA and DPDA.

Chomsky Hierarchy of languages: Type-0, Type-1, Type-2 & Type-3 languages, Recursive and recursively-enumerable languages.

Context free Grammars : Greibach Normal Form (GNF) and Chomsky Normal Form (CNF), Ambiguity, Parse Tree Representation of Derivations. Equivalence of PDA and CFG. Parsing techniques for parsing of general CFG – Early’s, Cook-Kassami-Younger (CKY) and Tomita’s parsing. RTNs, ATNs, Parsing of Ambiguous CFGs.

Linear Bounded Automata (LBA) : Power of LBA Closure properties.

Turing Machine (TM) : One tape, multi-tape, time and space complexity in terms of TM. Construction of TM, Computational complexity, Non-computability and Examples of non – computable problems.

5 Star
4 Star
3 Star
2 Star
1 Star

Enquire about this course