I know that $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, (l ≥ n) ∨ (l ≥ m)\}$ is a context-free language, because I know the context-free grammar, i.e.

$$ S \rightarrow AbZ \mid XBc \\ A \rightarrow aAb \mid X \\ B \rightarrow aBc \mid Y \\ X \rightarrow aX \mid a \\ Y \rightarrow bY \mid b \\ Z \rightarrow cZ \mid c $$

I have a bit of difficulties understanding this construction. Can you explain step-by-step how it has been created? The rules?

  • 1
    $\begingroup$ Instead of trying to understanding an existing grammar, I suggest you try to create a grammar yourself from scratch (without looking at that one) and see where it takes you! $\endgroup$ – D.W. Apr 21 at 17:04

Let us start by noticing that $X \to a^+$, $Y \to b^+$, $Z \to c^+$. Furthermore, $A \to a^n X b^n$ and $B \to a^m Y c^m$. Therefore $S$ generates words of the following two forms: $$ a^na^+b^nbc^+ \\ a^+a^mb^+c^mc $$ You take it from here.

  • $\begingroup$ You have modified my question with $S \rightarrow AbZ \mid XBc$. Are you sure this is correction? I had $S \rightarrow aAbZ \mid XBc$ $\endgroup$ – Robert Apr 21 at 21:42
  • $\begingroup$ Check out my answer and see for yourself. $\endgroup$ – Yuval Filmus Apr 21 at 21:43
  • $\begingroup$ I do understand what would do $A \rightarrow aAb \mid X$, $B \rightarrow aBc \mid Y$, $X \rightarrow aX \mid a$, $Y \rightarrow bY \mid b$ and $Z \rightarrow cZ \mid c$, but I have a bit of difficulties understanding what would do $S \rightarrow AbZ \mid XBc$. Could you add a bit more details? $\endgroup$ – Robert Apr 21 at 21:47
  • $\begingroup$ You’ll have to work out some of it on your own. $\endgroup$ – Yuval Filmus Apr 21 at 21:47
  • $\begingroup$ Ok, but this is precisely why I asked the question. The other rules seems to be obvious for me, but not the $S \rightarrow AbZ \mid XBc$. It might help if you could develop a bit more. $\endgroup$ – Robert Apr 21 at 21:50

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.