Programming
December 1, 2023Question 14173 – NIC-NIELIT STA 2020
December 1, 2023GATE 1997
|
Question 46
|
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'.
|
{w⊂wR|w ∈ {a,b}*}
|
|
|
{wwR|w ∈ {a,b,c}*}
|
|
|
{anbncn|n ≥ 0}
|
|
|
{w|w is a palindrome over {a,b,c}}
|
Question 46 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.
(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.
Correct Answer: A
Question 46 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.
(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.