automata - Is the following language context free grammar? -


for n>=0, given grammar (a^na^na^n) context free? tried using pumping lemma, , result was, no not context free.

for pumping lemma work need show, can find word , "pump up" in order break rules of pl.

in case have a^n a^n a^n , want split words word uv^kw still in specified grammar.

in case not work!

to see have think several cases:

1) u @ least 1 (as v cant empty definition of pl), making v , w rest of a's

2) u has lenght a^n, v has length of @ least a^n , w has length of a^n

3) ...

imagine have stencil of length k , put under every imaginable position of a^n a^n a^n so:

pumping lemma

if add 1 n, resulting word wont anymore in a^n a^n a^n, therefore pl fails. language a^n a^n a^n equals a^n b^n c^n standard example failing pl.

sidenote: if pl not fail cant conclude grammar context-free. pl works 1 direction.


Comments

Popular posts from this blog

Payment information shows nothing in one page checkout page magento -

tcpdump - How to check if server received packet (acknowledged) -