Context-Free vs. Regular Languages

COMP218 Lectures 2021-11-05

• Every regular language is context free.
• Not all context free languages are regular.

Regular to Context-Free Conversion

Regular Expression	Context Free Grammar
$\emptyset$	Grammar with no rules.
$\epsilon$	$S\rightarrow\epsilon$
$a$ (alphabet symbol)	$S\rightarrow a$
$E_1+E_2$	$S\rightarrow S_1\vert S_2$
$E_1E_2$	$S\rightarrow S_1S_2$
$E_1^*$	$S\rightarrow SS_1\vert\epsilon$

$S$ becomes that net start symbol.