Question

If L= {0^a1^b0^c : b ≠ a + c; a, b, c ≥ _0}, Is this language context free? If so can you give me PDA, CFG .

Answer 1

Logic for PDA:
strings are in this format: 0^a1^b0^c, where b!=a+c
so,initially for each 0 we push 0 to stack, which keeps the count of 0^a
then for each 1 we pop one 0 from stack
here we have there cases: if a<b,a>b and a=b
case1)a<b
means incoming 1's count is greater than the 0's in the stack
so,in this when ever the 0's in stack are empty, we stack pushing 1's for each 1, means now stack will contain 1^(b-a)
then after 1's are finished,stack will contain 1^(b-a)
then for each 0 we will pop one 1 from stack //here number of 0's must not equal b-a//that is c=b-a
if reading 0's is done, and stack is not empty then, we accept the string,move to final state//since c<b-a : b!=c+a
if still there are incoming 0's and stack is empty then, we accept the string,move to final state//since c>b-a :b!=c+a
if reading 0's is done, and stack is empty, then we reject
case2)a>b
means incoming 1's count is smaller than the 0's count in stack
this means, b!=a+c //since already a is greater than b
so, we can move to final state, and just read all remaining 0's : 0^c
case3)a=b
means reading 1's done and stack is empty
now
if at least 0 comes, then we accept, so move to final state// since b!=c+a
other wise we reject