edited by
545 views

1 Answer

Best answer
3 votes
3 votes

L  =  { abm  |  2n  <= m  <= 3n }  can be re written as :

    =  { an b2n }  U  { ab2n+1 } U ...................{ an b3n }

So if we see here the first component says that for every second 'b' that is read in input , pop an 'a' from the stack whereas for the last component { an b3n } , we pop an 'a' for every 3rd 'b' that is read in the input which is clearly a non deterministic behaviour as we dont know exactly when to pop 'a' as evident from above..

Hence the given language is NCFL.

selected by

No related questions found