TAC (B-TECH Computer Science Engineering 5th)

Section-A

Finite Automata and Regular Expressions: Finite State Systems, Basic Definitions Non-Deterministic finite automata

(NDFA), Deterministic finite automata (DFA), Equivalence of DFA and NDFA Conversion of NFA to DFA Finite automata with Emoves,

Regular Expressions, Equivalence of finite automata and Regular Expressions, Regular expression conversion and vice versa.

Introduction to Machines: Concept of basic Machine, Properties and limitations of FSM. Moore and mealy Machines,

Equivalence of Moore and Mealy machines, state and prove Arden‟s Method.

Section-B

Properties of Regular Sets: The Pumping Lemma for Regular Sets, Applications of the pumping lemma, Closure properties of

regular sets, Myhill-Nerode Theorem and minimization of finite Automata, Minimization Algorithm.

Grammars: Definition, Context free and Context sensitive grammar, Ambiguity regular grammar, Reduced forms, Removal of

useless Symbols, unit production and null production Chomsky Normal Form (CNF), Griebach Normal Form (GNF).

Section-C

Pushdown Automata: Introduction to Pushdown Machines, Application of Pushdown Machines

Turing Machines: Deterministic and Non-Deterministic Turing Machines, Design of T.M, Halting problem of T.M., PCP Problem.

 Section-D

Chomsky Hierarchies: Chomsky hierarchies of grammars, Unrestricted grammars, Context sensitive languages, Relation between

languages of classes.

Computability: Basic concepts, Primitive Recursive Functions.