Asked By : muradin
Answered By : akashchandrakar
z = uvwxy |vwx| <= n |vx| >= 1 forall i>=0, u v^i w x^i y in L
But if there exist u,v,w,x,y satisfying the first three constraints, we can show that there exists an i s.t. the fourth constraint fails. Case uvw consists only of “a”. Then when i=0, the string is not in L (fewer “a”s than “b”s or “c”s). Case vwx contains only “b”s – similar. Case vwx contains only “c”s – similar. Case vwx contains only two types of characters from {a,b,c}. Then uwy has more of the remaining type of characters. The string vw cannot contain “a”s, “b”s, and “c”s, since vwx is a substring of z and has length <=n (cannot contain the last “a” and the first “c” both).i.e this is a contradiction and our assumption is wrong that L is CFL.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33153