Problem Detail: I am having challenges (in two phases) with creating a CFG.
- Derive the CFG for the following language
- 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} $$
Asked By : Dennis
Answered By : Gilles
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14900
