## 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

### Pushdown Automata Question Bank

Pushdown Automata (PDA)  Question Bank

Question List - I

 Q.1 (a) Do as Directed. (i) Give Difference:Top-down Approach Vs Bottom-up Approach. 2 (ii) Specify the types of moves in PDA. 2 (iii) Is NPDA and DPDA Equivalent? Give Example. 1 (b) Write a Short note on Pushdown Automaton. 5 Q.2 (a) Obtain the CFG for following PDA.Give the Corresponding Leftmost Derivation for String : bacab 6

Question List - II

 Q.1 (a) Do as Directed. (i)   Give Difference : DPDA Vs. NPDA 1 (ii)  Define Acceptance by PDA / String Accepted by PDA. 2 (iii) Explain the Configuration/Instantaneous Description (ID) of PDA. 2 (b) Define PDA.Construct PDA for Language L = { x є {a, b}* | na (x) > nb (x) }Show the Sequence of Moves for Input String : bbabaa 5 Q.2 (a) Give Transition table and Transition Diagram for the Language of Palindrome. Draw Computation Tree for Input String aba. 6

Question List - III

 Q.1 (a) Do as Directed. (i)   Give Difference : NFA Vs. PDA 2 (ii)  Write a Short note on Parsing / Parser. 3 (b) Define DPDA. Construct DPDA for L = { xcxr  | x є {a, b}* , c є Σ* }ORConstruct PDA for Context Free Grammar S → aSa | bSb | c. 5 Q.2 (a) Define Top-down PDA Corresponding CFG.Construct Top-down PDA for given CFG.S → a | aS | bSS | SSb | SbS.Show the Sequence of Moves for Input String : abbaaa 6

### Context Free Grammar Question Bank

Context Free Grammar Question Bank

Question List - I

 Q.1 (a) Do as Directed. (i)   Define CFG. What is Meaning of Context Free? 2 (ii)  List out steps to convert CFG in to CNF 2 (iii) Define Inherently Ambiguous. 1 (b) Find out What Language is Generated by following CFG. 5 (i)  S → aT | bT | Λ.    T → aS | bS. (ii) S → aA | bC | b.   A → aS | bB.   B → aC | bA | a.  C → aB | bS Q.2 (a) Define Derivation Tree or Parse Tree.Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.S → aaaaS | aaaaaaaS | Λ. 5 (b) Prove that The Context Free Grammar G1 with ProductionsS1 → S1 + T | T   T   → T * F | F F   → ( S1 ) | ais Ambiguous. 5 OR (b) Find out CFG for L = { x є {0, 1}* | n0(x) = n1(x) } 5

Question List - II

 Q.1 (a) Do as Directed. (i)   List out Applications of CFG. 2 (ii)  Find out CFG for Regular Expression : (011 + 1)* (01)* 2 (iii) Define Linear Grammar. 1 (b) Find out CFG for given Language. 5 (i)  The Set of Odd-Length string in {a, b}* with middle Symbol a. (ii) The Set of Odd-Length string in {a, b}* whose first, middle, and last     Symbols are all the same. Q.2 (a) Define Leftmost and Rightmost Derivation.Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.S → A | B.   A → aAb | ab.   B → abB | Λ 5 (b) Define Nullable Variable and Unit Production.Find out CFG with no Λ- Productions and no Unit Productions.S → A | B | CA → aAa | BB → bB | bbC → aCaa | DD → baD | abD |aa 5 OR (b) Define Regular Grammar. Find a Regular Grammar generating L – {Λ} 5

Question List - III

 Q.1 (a) Do as Directed. (i)   Define Balanced Strings of Parentheses. 2 (ii)  Define CFL. List out Application of CFL. 3 (b) Find out CFG for (1)  L = { ai bj ck  | j=i or j=k }(2)  L = { ai bj   | i < 2j  } 5 Q.2 (a) Define An Ambiguous Grammar.Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.S → ABA.   A → aA | Λ.   B → bB | Λ 5 (b) Let G be the Context Free Grammar with ProductionsS → S + S | S * S | ( S ) | aand Let G1 be the Context Free Grammar with ProductionsS1 → S1 + T | T   T   → T * F | F F   → ( S1 ) | aThen L (G) = L (G1). 5 OR (b) Define CNF. Convert following CFG in to CNF.S → AACD.A → aAb | Λ                C → aC | aD → aDa | bDb | Λ 5

### NFA Question List

Non-Deterministic Finite Automata Question List

Question List - I

 Q.1 (a) Find out Regular Expression for Given Finite Automaton. 10 Q.2 (a) Give the Recursive Definition of δ* for an NFA. Using Subset Construction Draw FA for Given. 5 (b) If L subset of Σ* is a Language that is accepted by the NFA – Λ              M=(Q, Σ, q0, A, δ), then there is an NFA M1=(Q1, Σ, q1, A1, δ1) that also accepts L. 5 OR (b) Define Acceptance by an NFA. Check Whether the following strings are accepted by NFA or not.(1) abab         (2)  aaabbb 5

Question List - II

Q.1
(a)
Do as Directed.

(i)   Explain Relationship between DFA and NFA.
2

(ii)  Write down Statement & Application of Kleene’s Theorem  Part - I.
2

(iii) Non Recursive Definition of δ* for an NFA.
1

(b)
Prove that The Language accepted by any Finite Automata is Regular.
5
Q.2
(a)
Define δ* for an NFA-Λ Recursively.

Using Algorithm Draw an NFA accepting the same Language.
5

(b)
Define Λ – Closure of a Set of States for NFA-Λ.
A Transition table is given for an NFA- Λ with Seven States.

 q δ(q, a) δ(q, b) δ(q, Λ) 1 ø ø { 2 } 2 { 3 } ø { 5 } 3 ø { 4 } ø 4 { 4 } ø { 1 } 5 ø { 6, 7 } ø 6 { 5 } ø ø 7 ø ø { 1 }

Find:   (i)   Λ ({3,4})    (ii)    δ*(1, ab)
5

OR

(b)
Convert Given NFA in to Equivalent DFA Using Subset Construction Method.

5