Programming
December 1, 2023Question 14173 – NIC-NIELIT STA 2020
December 1, 2023Theory-of-Computation
Question 38 |
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 38 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 38 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.
Subscribe
Login
0 Comments