1
$\begingroup$

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot..

I have no idea what example is traditionally used for this.

$\endgroup$

1 Answer 1

3
$\begingroup$

The canonical example is the language $L=\{a^nb^n\mid n\ge 0\}$. It's easy to produce a CFG for this and it's nearly as easy to show that it's not a regular language. For your first question, note that any regular language can be generated by a left-linear grammar and these are CFGs, so any regular language is also context-free.

$\endgroup$
3
  • 1
    $\begingroup$ Showing that $L$ isn't regular is only easy if you already know how to do it. $\endgroup$ May 6, 2016 at 8:30
  • 1
    $\begingroup$ Could you please provide an example with a CFG and regular expression? $\endgroup$ May 6, 2016 at 8:40
  • 1
    $\begingroup$ A CFG for $L$ is given by the productions $S\rightarrow aSb\mid\epsilon$. There's no regular expression denoting that language. $\endgroup$ May 6, 2016 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.