CFG vs. Regular Expressions
CFG is more expressive than RE
- Every language that can be described by regular expressions can also be described by a CFG
Example languages that are CFG but not RE
- if-then-else statement, {anbn | n>=1}
Non-CFG
- L1={wcw | w is in (a|b)*}
- L2={anbmcndm | n>=1 and m>=1}