CODEWITHSUNDEEP
context-free-grammarregular-languageautomata
Sherry W. Birkin
Sherry W. Birkin

Reputation: 11

CFG to regular expression

Here is the grammar,

S -> A | B

A -> 0000A | epsilon

B -> 000B | epsilon

I thought the regular expression for above is

0000(0000)*000(000)* // because 0000 and 000 will be spotted at least once.

Is this correct ?

Some people said me that, this grammar is ambiguous. any one can explain this to me why?

Upvotes: 1

Views: 4459

Answers (2)

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58251

In following grammar (that is actually Right liner grammar) 

S -> A | B

A -> 0000A | epsilon

B -> 000B | epsilon

You can generate string from start variable S either via A or B so the language of grammar L(G) is Union (+) of two languages can be generat from A and B.

production: 

A -> 0000A | epsilon

generates (0000)* .

And

production: 

B -> 000B | epsilon

generates (000)*

So Regular expression for L(G) is: (000)* + (0000)*

note L(G) can have null string.

Upvotes: 2

Jim Lewis
Jim Lewis

Reputation: 45025

Your reasoning is not correct. Counterexample: the empty string is in the language, but your regex won't match it.

As far as ambiguity, consider a string of 12 zeroes. How many different ways can that be derived from that grammar?

Upvotes: 1

Related Questions