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 є Σ* }
OR
Construct 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 Productions
S1 → S1 + T | T  
T   → T * F | F
F   → ( S1 ) | a
is 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 | C
A → aAa | B
B → bB | bb
C → aCaa | D
D → 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.
SABA.   A → aA | Λ.   B → bB | Λ
5

(b)
Let G be the Context Free Grammar with Productions
S → S + S | S * S | ( S ) | a
and Let G1 be the Context Free Grammar with Productions
S1 → S1 + T | T  
T   → T * F | F
F   → ( S1 ) | a
Then L (G) = L (G1).
5


OR


(b)
Define CNF. Convert following CFG in to CNF.
S → AACD.
A → aAb | Λ               
C → aC | a
D → 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