2.39
Refer to Problem 1.41 for the definition of shuffle operation. Show that the class of context free languages is not closed under shuffle.
Solution:
A = {0n1n}
B = {anbn}
so 0pap1pbp ∈ SHUFFLE(A,B). Consider p to be pumping length.
Now it is clear if you pump from only from single type, then it won't be equal to its counter part like 1 for 0. If you consider to pump in two types, like 0s and a then also it will disturb count equality.
B = {anbn}
so 0pap1pbp ∈ SHUFFLE(A,B). Consider p to be pumping length.
Now it is clear if you pump from only from single type, then it won't be equal to its counter part like 1 for 0. If you consider to pump in two types, like 0s and a then also it will disturb count equality.
No comments:
Post a Comment