## Push-Down-Automata

 Question 1

Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?

 A L = {an bn│n ≥ 0} and is not accepted by any ﬁnite automata B L = {an |n≥0} ∪ {anbn|n ≥ 0} and is not accepted by any deterministic PDA C L is not accepted by any Turing machine that halts on every input D L = {an |n ≥ 0} ∪ {an bn |n ≥ 0} and is deterministic context-free
Theory-of-Computation       Push-Down-Automata       2016 set-01
Question 1 Explanation:
In this PDA, we can give labels to state as q0, q1, q2
where q0 and q2 are final states.
This PDA accepts the string by both ways i.e. by using q0 accepts as final state and by using q2 it accepts as empty stack.
Since q0 is initial as well as final state, so it can accept any number of a’s (including zero a’s) and by using q2 as empty stack it accept strings which has equal number of a’s and b’s (b’s comes after a’s).
Hence, L = {an | n≥0} ∪ { an bn | n≥0}.
 Question 2
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?
 A {anbncn ∣ n≥0} B {albmcn ∣ l≠m or m≠n} C {anbn ∣ n≥0} D {ambn∣ m,n≥0}
Theory-of-Computation       Push-Down-Automata       Gate 2006-IT
Question 2 Explanation:
At a time, the DPDA can compare 'a' and 'b' or 'b' and 'c' but not both.
To compare both conditions at the same time, we need a NPDA.
 Question 3
 A {albmcn | l = m = n} B {albmcn | l = m} C {albmcn | 2l = m+n} D {albmcn | m=n}
Theory-of-Computation       Push-Down-Automata       Gate 2006-IT
Question 3 Explanation: For every 'a' we put two X in stacks [at state S].
After that for every 'b' we pop out one X [reach to state t].
After that for every 'c' we pop out one X [reach to state u].
If all X are popped out then reached to final state f, means for every 'b' and 'c' there is 'a'. 'a' is followed by 'b' and 'b' is followed by 'c'.
Means,
Sum of no. of b's and no. of c's = twice of no. of a's
i.e., {albmcn | 2l = m+n}
 Question 4
Let LD be the set of all languages accepted by a PDA by final state and LE  the set of all languages accepted by empty stack. Which of the following is true?
 A LD = LE B LD ⊃ LE C LE = LD D None of the above
Theory-of-Computation       Push-Down-Automata       Gate-1999
Question 4 Explanation:
For any PDA which can be accepted by final state, there is an equivalent PDA which can also be accepted by an empty stack and for any PDA which can be accepted by an empty stack, there is an equivalent PDA which can be accepted by final state.
 Question 5
 A {w⊂wR|w ∈ {a,b}*} B {wwR|w ∈ {a,b,c}*} C {anbncn|n ≥ 0} D {w|w is a palindrome over {a,b,c}}
Theory-of-Computation       Push-Down-Automata       Gate-1997
Question 5 Explanation:
(A) w⊂wR, can be realized using DPDA because we know the center of the string that is c here.
(B) wwR, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {anbncn | n ≥ 0} is CSL.
(D) {w | w is palindrome over {a,b,c}},
is realized by NPDA because we can't find deterministically the center of palindrome string.
 Question 6
Give a deterministic PDA for the language L = {ancb2n|n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.
 A Theory Explanation is given below.
Theory-of-Computation       Push-Down-Automata       Gate-2001
There are 6 questions to complete.