Posts

Showing posts from June 6, 2010

Assignment - 13 Context Free and Non Context Free Grammar, Turing machines, & Recursively Enumerable Languages

B. H. Gardi College of Engineering and Technology,Rajkot Department of MCA MCA Semester – II Subject: 620007 – Theory of Computation
Assignment – 13 Context Free and Non Context Free Grammar, Turing machines, & Recursively Enumerable Languages


Context Free and Non Context Free Grammar 1 Pumping Lemma for CFG 2 Ogden’s Lemma Turing machines 3 Turing Machine (TM) 4 Configuration / Instantaneous Description (ID) of TM 5 What is meaning of Halting? 6 Acceptance by a Turing Machine (TM) 7 Finite Automata Vs. PDA Vs. Turing Machine 8 A TM Computing a Function 9 Computing a Numerical Function Recursively Enumerable Languages

Assignment – 12 Pushdown Automata

B. H. Gardi College of Engineering and Technology,Rajkot Department of MCA MCA Semester – II Subject: 620007 – Theory of Computation Assignment – 12  Pushdown Automata 

1 Pushdown Automata (PDA) 2 Configuration / Instantaneous Description (ID) of PDA 3 Deterministic PDA (DPDA) 4 Acceptance by PDA / String Accepted by PDA 5 Is DPDA and NPDA equivalent? Example. 6 NFA Vs. PDA 7 Top-down PDA Corresponding to a CFG. 8 Top-down Approach Vs. Bottom-up Approach 9 What is Parsing? / What is Parser?