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} $$


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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