1

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?

Improve this question
1
  • 1
    For an input of twelve zeroes, for example, you can't tell if it derives three As or four Bs. Commented Feb 9, 2013 at 1:48

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

@SherryW.Birkin Yes + is for Union in Regular expression.
@SherryW.Birkin Learn here + Operator in Regular Expression there is two kinds og + operators in RE
@GrijeshChauhan are there any clearly stated generalized set of rules / steps in any book / online to convert CFGs to Regexes?
@Mahesha999 "Regular Expression" is possible only for "Regular languages". So RE is possible for CFG if language is regular. And such CFGs can be converted into either "left linear grammar" to "right linear grammar" (L/RLG) and there are rules to write RE from L/RLGs. (if L/RLG can not be written from CFG than language is not a regular hance RE is not possible).
@Mahesha999 Additionally, there are rules to convert grammar into Left or Right linear grammar. You can find in a book "KLP mishra".
|
1

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?

Improve this answer

2 Comments

Oh hm ... thanks first but I then should I wrap them (0000)*(000)* ?
Try generating a regex for the language specified by A, then another for the language specified by B, then combining them into a regex that describes S. You'll probably need to use an alternation operator for that last step. This sounds like homework, so hopefully that's enough of a hint...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.