S -> aSb | A | B

A -> aS | a

B -> Sb | b

is this the language generated by this CFG? Or am I missing something?

enter image description here

  • 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

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


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.