Question 5306 – Higher-Education-and-Politics
February 16, 2024Question 13909 – Data-Structures
February 17, 2024GATE 2019
| Question 56 |
Which one of the following languages over Σ = {a,b} is NOT context-free?
| {wwR |w ∈ {a,b}*} | |
| {wanwRbn |w ∈ {a,b}*, n ≥ 0} | |
| {anbi | i ∈ {n, 3n, 5n}, n ≥ 0} | |
| {wanbnwR |w ∈ {a,b}*, n ≥ 0} |
Question 56 Explanation:
{wanwRbn |w ∈ {a,b}*, n ≥ 0} cannot be CFL.
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
Correct Answer: B
Question 56 Explanation:
{wanwRbn |w ∈ {a,b}*, n ≥ 0} cannot be CFL.
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
Subscribe
Login
0 Comments