CSPC-512 Theory of Computation
Teaching Scheme			Credit	Marks Distribution			Duration of End Semester Examination
L	T	P		Internal Assessment	End Semester Examination	Total
3	1	0	4	Maximum Marks: 40	Maximum Marks: 60	100	3 Hours
				Minimum Marks: 16	Minimum Marks: 24	40

Unit-I

Fundamentals: Automata Definition, applications, finite state machine, definitions, finite automaton model, acceptance of strings, deterministic finite automaton and non-deterministic finite automaton, transition diagrams.

Finite Automata: NFA with λ-transitions, equivalence of NFA & DFA, equivalence between NFA with and without λ-transitions, minimization of FSM, equivalence between two FSMs, finite automata with output- Moore and Melay machines.

Unit-II

Regular Languages: Regular sets, regular expressions, identity rules, constructing finite automata for a given regular expressions, Arden's theorem, conversion of finite automata to regular expressions, pumping lemma of regular sets, closure properties of regular sets, Myhill-Nerode theorem and minimization of finite automata, minimization algorithm.

Unit-III

Grammar Formalism: Regular grammars-right linear and left linear grammars, equivalence between regular linear grammar and FA, inter conversion, context free grammar, derivation trees, sentential forms, right most and leftmost derivation of strings.

Context Free Grammars: Ambiguity in context free grammars, minimization of context free grammars, Chomsky normal form, Greibach normal form.

Push Down Automata: Push down automata, definition, model, acceptance of CFL, acceptance by final state and acceptance by empty state and its equivalence, applications of push down machines.

Unit-IV

Turing Machine: Turing Machine, definition, model, design of TM, types of turing machines, post correspondence problems and halting problem of turing machine.

Chomsky Hierarchies: Chomsky hierarchies of grammars, unrestricted grammars, context sensitive languages, relation between languages of classes.