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
 



 

No comments:

Post a Comment