Course Name: CS2200 : Language Machines and Computations

Description: 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 membershi

Slot: D

RoomNo: CS34

Instructor: Kamala Krithivasan

Period: JAN-MAY 2013

This page was created on: Thursday 19th of September 2013 09:30:54 PM