[Solved]: Designing a CFG that produces as many c's as the difference of numbers of a's and b's

Problem Detail: 

The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is

$\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}; n = |l-m|\}$.

I have so far go to create the cfg for $(a^l)(b^m)$ but don't know how to do the one for $(c^n)$. It looks complicated as to find the value of n, we need to take the abs value for the difference between l and m. Can someone help?

And, here is the cfg I got so far for $(a^l)(b^m)$.

$S \to aS \mid bT|\epsilon $

$T \to bT \mid \epsilon$

I hope this is correct.

Asked By : SSH

Answered By : Patrick87

Yuval's answer is headed in the right direction: consider $L_1 = \{a^lb^mc^n \mid n = l - m\}$ and $L_2 = \{a^lb^mc^n \mid n = m - l\}$. Also, as he points out, it's helpful to think of these conditions as $l = n+m$ and $m = n + l$, respectively.

I propose the following grammar for $L_1$: $$S' \rightarrow aS'c \mid B' \mid \epsilon$$ $$B' \rightarrow aB'b \mid \epsilon$$

I propose the following grammar for $L_2$: $$S'' \rightarrow A''C''$$ $$A'' \rightarrow aA''b \mid \epsilon$$ $$C'' \rightarrow bC''c \mid \epsilon$$

Now, what remains is to show these grammars generate $L_1$ and $L_2$, after which you can give your answer as the following: $$S \rightarrow S' \mid S''$$

(You could even use just one symbol for $B'$/ $A''$, since they have the same rules.)

To show each of the proposed grammars works, you'll need to show two things: each proposed grammar generates only strings in the target language; each proposed grammar generates all the strings in the target language.

Arguing informally, we can say the proposed grammar for $L_1$ generates only strings in $L_1$ since whenever we add an $a$, we add either a single $b$ or a single $a$; furthermore, we have all $b$ coming after $a$, and all $c$ coming after $b$. To show that all the strings are generated, consider that applying the rule $S' \rightarrow aS'c$ a number of times equal to $\#_c(w)$, then the rule $S' \rightarrow B'$, then the rule $B' \rightarrow aB'b$ a number of times equal to $\#_b(w)$, then the rule $B' \rightarrow \epsilon$, yields the string $w = a^{\#_b(w)+\#_c(w)}b^{\#_b(w)}c^{\#_c(w)} \in L_1$ for any non-negative $\#_b(w), \#_c(w)$.

The arguments for the second proposed grammar are similar.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16608

3.2K people like this

 Download Related Notes/Documents