Friday 25 October 2013

Sipser 2.28 a. { w | in every prefix of w the number of a's is at least the number of b's }

2.28 a. { w | in every prefix of w the number of a's is at least the number of b's }

Hint:
Replace a with open bracket ( and b with closing  bracket ). You will get the big picture that he is talking about set of prefixes of balanced paranthesis language.

Solution:
Finding ambiguity free context free grammer is not that trivial.
Very first step to find an unambiguous grammar is finding a grammar, unambiguous or ambiguous.
Secondly, If you see the ambiguity in it then explore it to know it deeper. And set a priority rules set which will tell you which of the parse tree (derivation) you have to pick. And now set production rules.

Initially what clicked me is:
S → SS | (S) | ε
but it is ambiguous. Think !!

After trying a day or a couple, I figured out the grammar should be
S → (S)S | ε

But this is not what we were looking for but grammar in which every string's prefix have more ( than number of  ).
S → (S)S | (S | ε

Please correct me if I am wrong.

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete