Find a context-free grammar for $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N} + ∧ ((l ≥ n) ∨ (l ≥ m))\}$

168 Views Asked by At

I have to find a constext-free grammar for the language $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N} + ∧ ((l ≥ n) ∨ (l ≥ m))\}$. However, it seems hard to see where to start with the condition $((l ≥ n) ∨ (l ≥ m))$. All I know is we can't have strictly less number of a's than the number of b's or c's. I thought starting with $S \rightarrow XYZ$, but the rest is not that clear. Can you give a hint where to start?

EDIT

Can you tell if $S \rightarrow aAbc, S \rightarrow aBc$ with $A \rightarrow aAb, A \rightarrow a$ and $B \rightarrow aBc, B \rightarrow b$ is fine?

1

There are 1 best solutions below

4
On

I think this works: $$ S\to aAbc^+\mid a^+Bc$$ $$ A\to aAb\mid a^+$$ $$ B\to aBc\mid b^+$$

(where $x^+$ is short for $x^+\to xx^+\mid x$)