Convert regular expression to CFG

Question

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?

wondering whether there are any open source library implementations helpful for this task by now — matanster, May 26 '17 at 13:50

sdcvvc · Accepted Answer · 2014-12-20T23:32:12.743

16

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

edited Dec 20 '14 at 23:32

answered Apr 14 '10 at 17:31

sdcvvc

25,343
4
66
102

Why is **B -> 11** instead of **B -> B11**? – Siddharth Thevaril Dec 16 '14 at 23:19
Why are you changing `A+B` into `G -> A` and `G -> B`? Doesn't `+` mean "one or more of the previous expression" in regex? – Leon Overweel Dec 01 '17 at 04:25
@LeonOverweel In formal language theory `A+B` is used to denote sum, in programming languages notation `A|B` is used instead. – sdcvvc Jan 26 '18 at 22:26

Joey Adams · Answer 2 · 2010-04-14T17:33:24.470

I guess you mean convert it to a formal grammar with rules of the form V->w, where V is a nonterminal and w is a string of terminals/nonterminals. To start, you can simply say (mixing CFG and regex syntax):

S -> 01+10(11)*

Where S is the start symbol. Now let's break it up a bit (and add whitespace for clarity):

S -> 0 A 1 0 B
A -> 1+
B -> (11)*

The key is to convert *es and +es to recursion. First, we'll convert the Kleene star to a plus by inserting an intermediate rule that accepts the empty string:

S -> 0 A 1 0 B
A -> 1+
B -> (empty)
B -> C
C -> (11)+

Finally, we'll convert + notation to recursion:

S -> 0 A 1 0 B
A -> 1
A -> A 1
B -> (empty)
B -> C
C -> 11
C -> C 11

To handle x?, simply split it into a rule producing empty and a rule producing x .

score 2 · Answer 3 · answered May 15 '12 at 20:03

Actually, different CFG grammars can produce the same language. So given a regular expression (regular language), its mapping back a CFG is not unique.

Definitely, you can construct a CFG that result in a given regular expression. The above answers shown some ways to achieve this.

Hope this gives you a high level idea.

score 0 · Answer 4 · edited Aug 18 '22 at 18:55

0

For the example, the following grammar is equivalent:

S -> 01|10A
A -> 11A|empty

edited Aug 18 '22 at 18:55

trincot

317,000
35
244
286

answered Aug 17 '22 at 15:33

Muskan Kumari

1
1

Convert regular expression to CFG

4 Answers4

Linked