CODEWITHSUNDEEP
regexcontext-free-grammar
Arif H-Shigri
Arif H-Shigri

Reputation: 157

CFG to Regular expression

I am confused with this CFG. I want to convert it into a regular expression:

A -> aA | B | epsilon
B -> bB | A

Please also mention the conversion rule from CFG to RE.

Upvotes: 1

Views: 2389

Answers (1)

Lucas Trzesniewski
Lucas Trzesniewski

Reputation: 51430

I suppose you're talking about formal regular expression here.

Short answer: this is simply: (a | b)*.

Why? Let's see:

A -> aA | B | epsilon
B -> bB | A

This is equivalent to this grammar:

A -> aA 
A -> B
A -> epsilon
B -> bB
B -> A

See something here?

A -> B
B -> A

These are equivalent. Let's just replace B with A:

A -> aA 
A -> epsilon
A -> bA

Reorder this:

A -> aA 
A -> bA
A -> epsilon

Rewrite it with ORs

A -> aA | bA
A -> epsilon

Factor it:

A -> (a | b) A
A -> epsilon

Simplify:

A -> (a | b) A | epsilon

Which is:

A -> (a | b)*

Or, in concrete PCRE notation: [ab]*.

Also, it's not clear from your question, but you should be aware that only some CFGs can be translated to regular expressions.

Upvotes: 4

Related Questions