### 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
Prove that L = { a
^{i} b^{i }c^{j} | 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 2
^{h-1}
leaf nodes must have height greater than h.
| 3 | ||

(b) |
Prove that L = { x є {a, b, c}* | n
_{a}(x) < n_{b}(x) and n_{a}(x) < n_{c}(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 |

## Comments

## Post a Comment