Course info

Grammars - Production systems - Chomskian hierarchy - Right linear grammar and Finite state automata - Context free grammars - Normal forms - uvwxy theorem - Parikh mapping - Self embedding property - subfamilies of CFL - Derivation trees and ambiguity. Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Closure properties of CFL - Deterministic push-down automata. Turing machines - Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Recursively enumerable sets and recursive sets - Recursive functions - Time and space complexity measures - Context sensitive languages and linear bounded automata. Parsing - CYK algorithm - Deterministic bottom-up and top-down parsing - LR(k) and LL(k) grammars - Complexity of parsing algorithms, Lex and Yacc, Compiler tools. Decidability; Post's correspondence problem; Rice's theorem; decidability of membership, emptiness and equivalence problems of languages. Time and tape complexity measures of Turing machines; Random access machines; the classes P and NP; NP-completeness; Satisfiability and Cook's theorem; Polynomial reduction and some NP-complete problems. Computable functions; primitive recursive function; primitive recursive predicates; bounded and unbounded minimization; µ recursive functions - Godel numbering - equivalence to Turing computable functions.