Reputation: 157
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
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