2
$\begingroup$

I am pretty desperate finding the correct context free grammar for the following language: $$L=\{a^lb^mc^n \mid l,m,n \in \mathbb{N}_0, \, l\geq 2n+m\}$$

I would really appreciate if anyone could tell me how to generate the CFG from this language as I am stuck on this one for 2 days now.

I can't find a solution for adding the right amount of $b$'s and $c$'s to a generated string.

At the moment I have: $$ \begin{align*} S &\rightarrow aS \mid T \mid U \mid \varepsilon \\ T &\rightarrow aTb \mid \varepsilon \\ U &\rightarrow aaUc \mid \varepsilon \end{align*}$$

$\endgroup$
1
  • 2
    $\begingroup$ After rewriting into $\{ a^k a^{2n} a^m b^m c^n\mid k,m,n\ge 0 \}$, see accepted answer by @Apass Jack, the grammar can be constructed using the "basic toolbox". $\endgroup$ May 17, 2019 at 13:14

1 Answer 1

3
$\begingroup$

It might be easier than you have been thinking.

$$\begin{aligned} S&\rightarrow aS\mid U\\ U&\rightarrow aaUc\mid T\\ T&\rightarrow aTb\mid \epsilon \end{aligned}$$

The idea is to identify the language that could be obtained by a fixed operation that peels off some symbols. Peeling off $a$'s, we shrink words in $S$ to words in $U$. Peeling off some $a$'s and $c$'s, we shrink words in $U$ to words in $T$. $$\begin{aligned} S&=\{a^ka^{2n}a^mb^mc^n \mid k,m,n \in \mathbb{N}_0\}\\ U&=\{a^{2n}a^mb^mc^n \mid m,n \in \mathbb{N}_0\}\\ T&=\{a^mb^m\mid m \in \mathbb{N}_0\} \end{aligned}$$

$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.