Proof that there is unambigous grammar for every regular language

Problem Detail: How can I prove, or where can I find proof that for every regular language there is unambigous grammar?

Asked By : Josko

Answered By : Patrick87

Something like this might work. First, note that every regular language is accepted by some minimal DFA. Call such a DFA $M$. Next, describe how you could construct a right-regular grammar that accepts the same language as $M$. Take as your set of nonterminal symbols the set $Q$ of states of $M$. Form the set of productions as follows: the smallest set of productions such that if $M$ has a transition from $q_1$ to $q_2$ on $sigma$, then there is a production $q_1 rightarrow sigma q_2$, and also a production $q_1 rightarrow sigma$ if $q_2$ is an accepting state. (You’ll also need to add the production $q_0 rightarrow epsilon$ if the empty string is in the language). Now, if this grammar is ambiguous, there are two different derivations for some string. This would imply that, at some point, more than one transition was available in the minimal DFA (since each production corresponds to some transition). This is a contradiction, since there cannot be more than one valid transition at any time while a DFA processes input. Basically, while you’re very right that right-regular grammars can be ambiguous, you can actually construct a specific right-regular grammar that must be unambiguous. All you have to do is describe the method of construction and produce a valid argument why it’s right-regular and why it can’t be ambiguous.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16082

Leave a Reply