CSE 417

Alphabet, string (finite and infinite) and languages. Finite representation of languages. Finite automation (deterministic, non-deterministic and Internating), regular expressions, left and right linear grammars and their equivalence’s- Minimal machine, simplification of regular expression. Finite state transducer. Properties of regular languages: closure properties, pumping theorem, ultimately periodic set. Algorithmic problems. Chomsky hierarchy of languages. Pushdown automaton (non-deterministic, deterministic and their non equivalence), context free grammars and their equivalence. Reduce grammars normal forms. CKY and Barley’s parsing algorithms. Ambiguity: deterministic CFL and LR grammars. Properties of CFL: closure properties, pumping theorem Parikh’s theorem Formal power series and degree of ambiguity. Fixed point theory. Algorithmic properties. Turing machine type-O grammar and their equivalence. TM as a transducer, recognizer, acceptor. Variants of TM. Turing acceptable and recognizable languages (recursive and recursively innumerable sets). Universal TM. Halting problem of TM and undecidability results (related to language theory e.g. equivalence of CFGs, ambiguity of CFG etc) Non-deterministic linear space bounded TM (liner bounded automata) and context-sensitive language (CSL ). Properties of CSL. Finite automation on infinite strings. Buchi and Mcnaughton finite state machines, their languages and properties, Relation of these machines and languages with logic and concurrency. Fractal images and automation on infinite strings.