Sunday, December 18, 2011

Turing Machine Question Bank

Turing Machine (TM) Question Bank

Question List - I



Q.1
(a)
Do as Directed.



(i)   Give Difference: TM Vs. PDA.
1


(ii)  Define A TM Computing a Function.
1


(iii) Define A TM Enumerating a Language
1


(iv)  Define Configuration / Instantaneous Description (ID) of TM
2

(b)
Define Pumping Lemma for CFL.
Prove that L = {  ss | s є {a, b}* } is not Context Free.
5
Q.2
(a)
Write a Short note on Turing Machine.
5

(b)
Write a Short note on Chomsky Hierarchy.
5



Question List - II



Q.1
(a)
Do as Directed.



(i)   Give Difference: TM Vs. FA.
1


(ii)  Define Acceptance by TM.
1


(iii) Define Recursively Enumerable Language.
1


(iV) Explain Context-Sensitive Grammar (CSG)
2

(b)
Define Turing Machine.
Construct TM Accepting Language pal of Palindrome.
Show the Sequence of Moves for Input String (1) ab (2) bab
5
Q.2
(a)
Define Ogden’s Lemma.
Prove that L = { ai bi cj | j ≠ i} is not Context Free Language.
5

(b)
Explain Chomsky Hierarchy in brief.
5



Question List - III



Q.1
(a)
Do as Directed.



(i)   List out the Possibilities when TM processes an Input String?
1


(ii)  Define Linear Bounded Automaton (LBA).
 1


(iii) Prove that For any h ≥ 1, a Binary Tree having more than 2h-1
      leaf nodes must have height greater than h.
3

(b)
Prove that L = { x є {a, b, c}* | na(x) < nb(x) and na(x) < nc(x) } is not Context Free Language.
5
Q.2
(a)
Define Computing a Numerical Function.
Construct TM to compute n mod 2.
Show the Sequence of Moves for (1) n=2  (2) n=3
5

(b)
Write a Short note on Hierarchy of Grammar.
5

No comments:

Post a Comment