Derive a Context Free Grammar from a language

Question

I am having challenges (in two phases) with creating a CFG.

1. Derive the CFG for the following language
2. Show parse trees for the strings cacab and aacabbb obtained from the grammar designed above.

I am getting a bit mixed up by the exercise especially because my CFG appears not to produce a parse tree.

Here is the language:

$$ L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \} $$

So far my grammar looks as follows:

$$ \begin{align} S &\to Ab \mid Bb \mid Cb \mid b \\ A &\to aA \mid \epsilon \\ B &\to caB \mid \epsilon \\ C &\to bC \mid \epsilon \\ \end{align} $$

Answer 1

You're on the right track: $A$ recognizes $a^*$ (i.e. $\{a^n \mid n \ge 0\}$), $B$ recognizes $(ca)^*$ and $C$ recognizes $b^*$.

You need to assemble them correctly. $Ab | Bb | Cb | b$ recognizes words that are made of something recognized by $A$ followed by $b$, or of something recognized by $B$ followed by $b$, etc. A word in $L$ consists of a part that's recognized by $A$ followed by a part that's recognized by $B$, etc. So the pieces need to be concatenated together: $S_1 \to ABCb$.

$S_1$ recognizes $\{a^n (ca)^m b^{p+1} \mid m,n,p \ge 0\}$. This is too much: $L$ consists only of the words for which $n = p$ in this decomposition. Instead of defining $A$ and $C$ separately, you need to relate them. Whenever you put an $a$ on the left of the $B$ part, put a $b$ on the right. $$ \begin{align} S_2 &\to B \\ S_2 &\to a S_2 b \\ \end{align} $$ This constraints the number of $a$'s on the left to be equal to the number of $b$'s on the right. The words in $L$ actually have one more $b$ on the right. One way to add that $b$ is to append it at the end: $$ S \to S_2 b $$ Another approach is to tack on the $b$ to the end of the $B$ part. $S$ and $S'$ recognize the same language, with slightly different parse trees. $$ \begin{align} S' &\to B b \\ S' &\to a S' b \\ \end{align} $$

To construct the parse trees, work out where each rule is applied to recognize the sample words.