S -> aSb | A | B
A -> aS | a
B -> Sb | b
is this the language generated by this CFG? Or am I missing something?
$\begingroup$
$\endgroup$
-
2$\begingroup$ What have you tried towards proving your claim? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael♦ May 14 '17 at 19:15
-
$\begingroup$ Quasi-duplicate reference question. $\endgroup$ – Raphael♦ May 14 '17 at 19:15
-
$\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael♦ May 14 '17 at 19:16
-
$\begingroup$ I tried different combinations of what I can get from this CFG, and it turned out to be something like: {a, b, ab, aba, abab, ba, baba} etc. hence the claim. $\endgroup$ – Dan Danielson May 14 '17 at 19:17
$\begingroup$
$\endgroup$
A technique that can be useful here is to eliminate some of the variables. Since $A$ can only be replaced by $aS$ or $a$ and $B$ by $Sb$ or $b$ we have the equivalent grammar $$ S\rightarrow aSb\mid aS\mid a\mid Sb\mid b $$ Now notice that in any sentential form in a derivation we can only add $a$s to the left of $S$ and we can only add $b$s to the right, so any string of terminals derived from the start variable must have the form $a^mb^n$. Finishing off, we see that $S$ must eventually be replaced by one of $a$ or $b$, so we see that your proposed answer was almost correct: $$ L(G) = \{a^mb^n\mid m,n\ge 0\text{ and }m,n\text{ not both }0\} $$ or, if you prefer a slightly nonstandard regular expression-ish version $$ a^*b^*\setminus\epsilon $$
answered May 15 '17 at 12:53
