I am trying to decide whether the following language is context free:

$$L = \{ a^nb^{3n}c^n \, | \, n \geq 0 \} $$

Assume $L$ is context-free. Let $p$ be the pumping length given by the Pumping Lemma. Choose string $s = a^pb^{3p}c^p ∈ L$. Then, $|s| ≥ p$. Take an arbitrary decomposition $s = uvxyz$ where $|vxy| \le p$ and $|vy| > 0$.

Case 1:

i. $v,y ∈ a^*$

ii. $v,y ∈ b^*$

iii. $v,y ∈ c^*$

Here, uv0xy0z ∉ L, due to incorrect number of symbols.

Case 3: i. $$v ∈ aa* and y ∈ bb*$$ ii. $$v ∈ bb* and y ∈ cc*$$

Here, uv0xy0z ∉ L, since #a's ≠ #c's.

So, s cannot be pumped, which contradicts the Pumping Lemma. Hence, L is not context-free.

However, after checking my answer, it seems that I missed that I missed one case where:

$$ v ∈ aa^*bb^* or \,\,y ∈ aa^*bb^* $$ $$ v ∈ bb^*cc^* or \,\,y ∈ bb^*cc^* $$

Here, uv2xy2z ∉ L, due to incorrect ordering of symbols.

But this doesn't make sense to me; how can this mess up the ordering of the symbols because wouldn't it follow that for example X would be the symbols after v?

Thanks guys,

  • $\begingroup$ Could someone fix my equations at the end also btw; I'm not sure why it didn't format correctly. $\endgroup$
    – Priit
    Commented Sep 7, 2023 at 7:16
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – D.W.
    Commented Sep 7, 2023 at 15:51
  • $\begingroup$ Note that in math mode you need to use \{, rather than {. Also in math mode, use * rather than \*. $\endgroup$
    – D.W.
    Commented Sep 7, 2023 at 15:52
  • $\begingroup$ I edited the beginning of the question to help, but please edit the rest to make it readable. $\endgroup$ Commented Sep 20, 2023 at 19:17
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented Sep 20, 2023 at 19:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.