Friday 15 November 2013

Refer to Problem 1.41 for the definition of shuffle operation. Show that the class of context free languages is not closed under shuffle.

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. 

No comments:

Post a Comment