0
$\begingroup$

Language:

$ L = a^{n+m}b^{n}c^{m} $

As per a recent test I gave, this language is not context free.

However, I think it is.

Corresponding Grammar:

$ X \rightarrow aXY \space |\space \epsilon $

$ Y \rightarrow b \space | \space c $

Pushdown Automata:

Keeping pushing all $a$ to the stack, until a $b$ is scanned. Keeping popping $a$ from stack for each character scanned, until end of input.

If, after the end of input the stack is empty accept the string. Else, go to non-accepting state.

Please let me know if I'm thinking along the right lines or if I've missed something..

$\endgroup$
  • $\begingroup$ Has been asked before... $\endgroup$ – Yuval Filmus Feb 3 '14 at 15:01
  • $\begingroup$ @YuvalFilmus Where? $\endgroup$ – Raphael Feb 3 '14 at 16:17
  • $\begingroup$ @Raphael I don't remember, and it is rather hard to search for these things. Perhaps it was $a^n b^{n+m} c^m$ rather than this language. $\endgroup$ – Yuval Filmus Feb 3 '14 at 16:27
  • $\begingroup$ Yeah, neither google nor StackExchange search can take MathJax, so I couldn't find if there's a duplicate.. $\endgroup$ – sanjeev mk Feb 3 '14 at 16:48
  • 1
    $\begingroup$ Actually, SE can search for LaTeX (it's just text on their end); you readily find this question which is indeed equivalent. (cc @YuvalFilmus) $\endgroup$ – Raphael Feb 3 '14 at 17:16
4
$\begingroup$

the corresponding grammar you gave would accept aaaabcbc. A better grammar for this problem would be

$X \rightarrow aXc$

$X \rightarrow aYb$

$X \rightarrow \lambda$

$Y \rightarrow aYb$

$Y \rightarrow \lambda$

where $\lambda$ is empty string.

$\endgroup$
  • $\begingroup$ Thanks , this grammar works..I wonder why my prof thinks this language is not context free.. $\endgroup$ – sanjeev mk Feb 3 '14 at 15:02
  • $\begingroup$ @sanjeevmk Who can say? But a good intuition about why this language should be context free is that it's essentially $(^m[^n]^n)^m$ with the brackets spelled in a funny way, and well-matched brackets are the stereotypical context-free language. $\endgroup$ – David Richerby Dec 14 '14 at 16:31
3
$\begingroup$

Hint for constructing a grammar: $a^{n+m} b^n c^m = a^m (a^n b^n) c^m$.

Hint for constructing a PDA: start with a PDA for $a^{n+m} b^{n+m}$.

As a bonus, you can try to solve both parts for the language $\{ a^{n+m+k} b^n c^m d^k : n,m,k \geq 0 \}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.