# Context-free grammar for $\{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$

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?

• 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! – 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.
• You have modified my question with $S \rightarrow AbZ \mid XBc$. Are you sure this is correction? I had $S \rightarrow aAbZ \mid XBc$ – Robert Apr 21 at 21:42
• 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? – Robert Apr 21 at 21:47
• 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. – Robert Apr 21 at 21:50