# How can I show context free grammars are strictly more expressive than regular expressions with an example?

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.

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.

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