My problem of understanding is how to create a new a before the b's if you create new c's.
Hopefully someone can help me out.
1
-
$\begingroup$ cs.stackexchange.com/q/18524/755 $\endgroup$– D.W. ♦May 27 at 16:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can firstly spawn $k$ letter $c$'s providing an $a$ for every $c$ spawned, then start putting $m$ $b$'s between $a$ and $c$ adding $a$ for every $b$. Also letter $a$ can be created any number of times after all $b$ and $c$ letters are created. This approach can be done with the following CFG: $$G = (V, \Sigma, S, R), \: V = \{S, A, B, B', C, C'\} \cup \Sigma,$$ and the rules are $$R = \begin{cases} S \to AC, \\ S \to AB, \\ C \to ACC', \\ C \to AC', \\ C \to ABC', \\ B \to ABB', \\ B \to AB', \\ C' \to c, \\ C' \to e, \\ B' \to b, \\ B' \to e, \\ A \to Aa, \\ A \to a. \end{cases}$$ This grammar is definetely not the most beautiful and short, I have put some safety checks there. However, it demonstrates the idea of my solution.
