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?

Wooble
  • 87,717
  • 12
  • 108
  • 131
Sherry W. Birkin
  • 11
  • 1
  • 3

2 Answers2

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.

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • @SherryW.Birkin Yes `+` is for Union in Regular expression. – Grijesh Chauhan Feb 09 '13 at 09:25
  • @SherryW.Birkin Learn here [**`+` Operator in Regular Expression**](http://stackoverflow.com/questions/14122755/what-will-be-the-dfa-for-the-regular-expression-00101011?answertab=votes#tab-top) there is two kinds og `+` operators in RE – Grijesh Chauhan Feb 09 '13 at 10:33
  • @GrijeshChauhan are there any clearly stated generalized set of rules / steps in any book / online to convert CFGs to Regexes? – Mahesha999 Jan 10 '17 at 08:51
  • @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). – Grijesh Chauhan Jan 10 '17 at 10:05
  • @Mahesha999 Additionally, there are rules to convert grammar into Left or Right linear grammar. You can find in a book "KLP mishra". – Grijesh Chauhan Jan 10 '17 at 10:06
  • Rules for converting any CFG to L/RLG. Do you mean to say steps for eliminating direct left(/right) recursion i.e. replacing A→Aα|β (which is left recursive) with {A→βA',A'→ϵ | αA'}(which is right recursive)? Also, I know how to convert LLG to RLG and vice versa. LLG2RLG: (LLG of L) -reversed-> (RLG for L^R) --> (FA for L^R) -reversed-> (FA for L) --> (RLG for L). Having Ullman, Linz & two more local books. Still unaware of steps for converting **ANY** CFG to L/RLG & L/RLG to regex. Can u elaborate? Or share pics of relevant pages? --> – Mahesha999 Jan 10 '17 at 10:34
  • <-- also did u meant steps to convert RLG to NFA as explained [here](http://stackoverflow.com/a/13222176/1317018)? – Mahesha999 Jan 10 '17 at 10:35
  • *Not any* CFG. But *a* CFG if and only if Language of CFG is Regular. "By seeing just grammar rules we can not tell that weather language is regular or not", and so indeed you can not find any book having lecture to convert CFG into RE - it is not always possible. ["You can write RE from CFG by analyzing"](http://stackoverflow.com/questions/22994440/converting-context-free-grammer-into-regular-expression) – Grijesh Chauhan Jan 10 '17 at 10:38
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?

Jim Lewis
  • 43,505
  • 7
  • 82
  • 96
  • Oh hm ... thanks first but I then should I wrap them (0000)*(000)* ? – Sherry W. Birkin Feb 09 '13 at 01:24
  • 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... – Jim Lewis Feb 09 '13 at 01:28