Other university all, Computer Engineering , Automata Theory Syllabus

Automata Theory

Regular Languages and Finite Automata

Proofs,RecursiveDefinitions,Regularexpressionsandregularlanguages,Finite
Automata,unions,intersection&complementsofregularlanguages,Applications 
of FA

Nondeterminism and Kleene’s Theorem
Nondeterministic finite automata, NFA with null transition, Equivalence of FA’s,
Kleene’s Theorem (Part I & Part II), Minimal Finite Automata

Context free Grammars
Definition, Union, Concatenation and Kleene *’s of CFLs, Derivation trees and
ambiguity, Simplified forms and normal forms

Parsing andPushdownAutomata 
Definition of Pushdown Automata, Deterministic PDA, Equivalence of CFG’s&
PDA’s, Top down parsing, bottom up parsing.

Context free languages
CFL’s and non CFL’s, Pumping Lemma, intersections and complementsof CFLs

Turing Machines
Definition,TMaslanguageacceptors,combiningTuringMachines,Computing 
partial function with a TM, Multi-tape TMs, and Universal TM