Tuesday, June 8, 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
10
Accepting a Language and Recognizing a Language
OR
Recursively Enumerable 
OR
Turing Acceptable
OR
Turing Decidable
11
A TM Enumerating a Language
12
Context-Sensitive Language (CSG)
13
Linear-Bounded Automata (LBA)
14
Chomsky Hierarchy
 



 

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?