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


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.

  • $\begingroup$ Thank you.. I figured the same thing myself, but anyway this helps a lot as reasuring :) $\endgroup$ – Josko Oct 14 '13 at 22:04

Hint: Use a right-regular grammar. This is a kind of grammar which has rules of the following types: $A \to aB$ and $A \to \epsilon$.

  • $\begingroup$ That was my first thought but you even right regular grammar could be ambigous, for example - pastebin.com/yXKtfrz0 $\endgroup$ – Josko Oct 14 '13 at 19:09
  • 1
    $\begingroup$ If you construct your grammar from a DFA (rather an NFA) then the result would be unambiguous. $\endgroup$ – Yuval Filmus Oct 14 '13 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.