Formal
Languages
and the
Theory of
Computation

Spring 2006
course
navigation

Regular Expressions to CFG

Regular Expressions embedded in a CFG can be converted to normal CFG rules as follows:
For X -> A* :
X -> e X -> D X -> DD D -> A
For Y -> A.B :
Y -> AB
For Z -> AUB :
Z -> A Z -> B