[Solved]: What does this context-free grammar generate?

Problem Detail: 

The grammar is

$$ S\to aSb\ |\ bSa\ |\ SS\ |\ \epsilon. $$

I think this generates the set of strings with equal numbers of $a$'s and $b$'s based on examples I've done. Is this correct?

Asked By : redundant6939

Answered By : Patrick87

This doesn't seem particularly rigorous as far as arguments go, but it's early here. Besides, this might help with intuition.

To see that the grammar generates words in the language, consider that every rule which adds either $a$ or $b$ adds an equal number of the two. Therefore, any string the grammar generates must have equal numbers of the two symbols.

To see that any word in the language can be generated by the grammar, consider any word $w$. We can definitely write $w$ as one of the following:

1. $w = axa$
2. $w = axb$
3. $w = bxa$
4. $w = bxb$

In cases 2 and 3, we can have applied the productions $S \rightarrow aSb \mid bSa$; we have that $w$ can be generated by our grammar if $x$ can. We also have that $|x| < |w|$. In cases 1 and 4, we must have used the rule $S \rightarrow SS$ to get $w$; let us now write $w = xy$ where $x$ and $y$ are also strings in the language (exercise: show this is always possible in the cases considered). We have $|x|, |y| < |w|$.

Both strings of length 2 in the language can be generated by the grammar (we could choose the empty string as the base case instead, might make more sense). By recursively applying the analysis in the preceding paragraph, we can find a way to generate any string in the language (since all words are even length, child words are shorter than parent words, and length 2 is the base case).

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents