Sunday, December 18, 2011

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

No comments:

Post a Comment