0
$\begingroup$

Okay so here's my current solution for the question that asks whether the language is context free:

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

Assume by contradiction that L is context-free. Let p be the pumping length given by the Pumping Lemma. Choose string $$s = a^pb^{3p}c^p ∈ L$$. |s| ≥ p. Take an arbitrary decomposition s = uvxyz where |vxy| ≤ 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,

$\endgroup$
5
  • $\begingroup$ Could someone fix my equations at the end also btw; I'm not sure why it didn't format correctly. $\endgroup$
    – Priit
    Sep 7 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.
    Sep 7 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.
    Sep 7 at 15:52
  • $\begingroup$ I edited the beginning of the question to help, but please edit the rest to make it readable. $\endgroup$ Sep 20 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
    Sep 20 at 19:17

0

Your Answer

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