Convert regular expression to CFG

regex grammar automata

Prasoon Saurav · Apr 14, 2010 · Viewed 29k times · Source

How can I convert some regular language to its equivalent Context Free Grammar? Is it necessary to construct the DFA corresponding to that regular expression or is there some rule for such a conversion?

For example, consider the following regular expression

01+10(11)^*

How can I describe the grammar corresponding to the above RE?

Answer

Change A+B to grammar
```
G -> A
G -> B
```
Change A* to
```
G -> (empty)
G -> A G
```
Change AB to
```
G -> AB
```

and proceed recursively on A and B. Base cases are empty language (no productions) and a single symbol.

In your case

 A -> 01
 A -> 10B
 B -> (empty)
 B -> 11B

If the language is described by finite automaton:

use states as nonterminal symbols
use language as set of terminal symbols
add a transition p -> aq for any transition p -> q on letter a in the original automaton
use initial state as initial symbol in the grammar

Convert regular expression to CFG

Answer

Related questions