Provides Information regarding Theory Of Computation And Compiler Design taught at VIT (VIT BHOPAL UNIVERSITY) (VELLORE INSTITYTE OF TECHNOLOGY)
(1)
Basic concepts – Theorem proving – Finite automata: NFA, DFA, € - NFA, Regular expressions - Equivalence between FA and RE – Minimization – Decision properties – Pumping lemma for Regular Languages. Problems: Design of FA – Inter-conversion between RE and FA – Proving languages to be not regular
(2)
Specification of tokens – FA and RE to represent token formats – LEX. Context Free Grammar – Derivations – Parse trees – Ambiguity – Pushdown Automata – DPDA & NPDA – Decision properties – Pumping lemma for CFL. Problems: Design of CFG – Design of PDA – Inter-conversion between PDA & CFG – Proving languages to be not context- free
(3)
Chomsky Normal Form – Griebach Normal Form – Parsing – Top-down Parsing – Predictive Parsing - Bottom up parsing – SLR, CLR and LALR Parsing – YACC. Problems: Conversion from CFG to CNF, GNF – Parsing
(4)
Turing machines – TM as a computation model – TM as a recognizer – TM with multiple tapes – Other models of TM – Linear Bounded Automata. Three Address Codes – Code optimization techniques. Problems: Design of TM – Design of LBA – Conversion from parse tree to TAC – optimization techniques
(5)
Chomsky Hierarchy of languages – Undecidability – Recursive and non – recursive languages – Examples - Code generation. Problems: Identification of Undecidability – Code generation
- Educational Purpose
- Open Source Licensed.