Question 5306 – Higher-Education-and-Politics
February 16, 2024Question 13909 – Data-Structures
February 17, 2024Question 7822 – Theory-of-Computation
Which one of the following languages over Σ = {a,b} is NOT context-free?
Correct Answer: B
Question 4 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.
{wwR |w ∈ {a,b}*}
{wanwRbn |w ∈ {a,b}*, n ≥ 0}
{anbi | i ∈ {n, 3n, 5n}, n ≥ 0}
{wanbnwR |w ∈ {a,b}*, n ≥ 0}
Subscribe
Login
0 Comments