Push-Down-Automata

Question 1
A
50
Theory-of-ComputationPush-Down-AutomataGATE 2021 CS-Set-1Video-Explanation
Question 1 Explanation: 

Question 2

Let Q = ({q1,q2}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents. 

(1) δ(q1,a,Z) = {(q1,Za)}
(2) δ(q1,b,Z) = {(q1,Zb)}
(3) δ(q1,a,a) = {(.....,.....)}
(4) δ(q1,b,b) = {(.....,.....)}
(5) δ(q2,a,a) = {(q2,ϵ)}
(6) δ(q2,b,b) = {(q2,ϵ)}
(7) δ(q2,ϵ,Z) = {(q2,ϵ)}
A
Theory Explanation.
Theory-of-ComputationPush-Down-AutomataGATE 1996
Question 3

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata? 

 Note: wR  is the string obtained by reversing 'w'.
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-ComputationPush-Down-AutomataGATE 1997
Question 3 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.
There are 3 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access