Operation Research

Chromsky hierarcy: Type 0, type 1, type 2 and type 3 grammar. Finite automata, Deterministic and non deterministic finite automata, Conversion of non deterministic finite automata to deterministic finite automata, Regular expression and their relationship to finite automata. Pushdown automata, contex free grammars: Deterministic and non deterministic pushdown automata. Context free grammars; Useless productions and emptiness set; Ambiguity; context free grammars for pushdown automata and vice-versa. Properties of context free languages, pumping lemma, closure properties, existence of non-context free languages. Turing machines, Decidability and undecidability.