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$
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$
  • 1
    $\begingroup$ Showing that $L$ isn't regular is only easy if you already know how to do it. $\endgroup$ – Yuval Filmus May 6 '16 at 8:30
  • 1
    $\begingroup$ Could you please provide an example with a CFG and regular expression? $\endgroup$ – Dhruv Ghulati May 6 '16 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$ – Rick Decker May 6 '16 at 13:12

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.