Cfg doubt

Question

1) Is the language L = { a^n+m b^n+m  c^m   | n,m>=0 }  a Cfl????

Answer 1

Given language L = {a^n+m b^n+m c^m  | n,m >= 0}

(or)                  L = {a^m+n b ^n+m c^m | n ,m >= 0}        ..........(2)

(or)                  L = {a^n+m b^m+n c^m  | n,m >= 0}         ...........(3)

I have written in different ways to make understand if we can model a PDA using (2) and (3) .First let us try to construct using (2) 

a) In this we push first m a's into the stack , the  n  a's into the stack .After this b is read and hence n a's are popped then m a's .This completes the reading of 'b' and involvement of stack is over as well.So it can keep into memory what is the "m" 

Similarly we can also proceed for the next representation that I have shown.Both are one and the same.Hence since we are not able to keep track of variable 'm' as a^n+m b^n+m part is over and hence stack is empty , the language hence cannot be modelled using a single stack and hence cannot be modelled using a PDA.

Hence the given language is not CFL.

Comments

Nice explanation.