Previous year question paper for TOC (B-TECH computer science engineering 7-8th)

 Module 1:

 Basics of Strings and Alphabets

Module2: 

Finite Automata – DFA, transition graphs, regular languages, non-deterministic FA, equivalence of

DFA and NDFA

Module3:

 Regular grammars, regular expressions, equivalence between regular languages, properties of

regular languages, pumping lemma.

Module4:

 Context Free Languages – Leftmost and rightmost derivation, parsing and ambiguity, ambiguity in

grammar and languages, normal forms

Module5:

 Pushdown Automata – NDPDA, DPDA, context free languages and PDA, comparison of

deterministic and non-deterministic versions, closure properties, pumping lemma for CFL

Module6: Turing Machines, variations, halting problem, PCP

Module7:

 Chomsky Hierarchy, LR(k) Grammars, properties of LR(k) grammars, Decidability and Recursively

Enumerable Languages