# Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?

Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous? According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars generating them. Every regular language is also DCFL, hence they will follow the same, but I doubt if every grammar corresponding to a DFA is non-ambiguous and that of NFA is ambiguous.

• What do you mean by "a grammar corresponds to an automaton"? Jan 7, 2018 at 19:58
• Hint: A non-deterministic grammar can be unambiguous. Jan 7, 2018 at 19:58
• Hint: There are infinitely many regular grammars (and automata) for every regular language -- some of them deterministic, some non-deterministic, and some ambiguous. Jan 7, 2018 at 19:59
• what i mean is we can draw a DFA or a NFA and convert it into right linear grammar (rlg) Jan 8, 2018 at 5:21

Let us consider the following construction of a regular grammar from an NFA. We will have a non-terminal $S_q$ for each state $q$. The starting symbol is $S_{q_0}$. If there is a transition from $q$ to $q'$ upon reading $\sigma$ (possibly $\sigma = \epsilon$), then we add the transition $S_q \to \sigma S_{q'}$. If $q$ is an accepting state, we add the transition $S_q \to \epsilon$. Whether the result is a regular grammar or not depends on your definition of a regular grammar (and on whether you allow $\epsilon$ transitions), but let's ignore this aspect.
You can check that this grammar is unambiguous if and only if, each word $w$ accepted by the NFA has a unique accepting path in the NFA, where an accepting path is something that looks this way: $$q_0 \xrightarrow{\sigma_0} q_1 \xrightarrow{\epsilon} q_2 \to \cdots \to q_f,$$ where $q_f$ is an accepting state, and the symbols on top of the arrows spell $w$. Such an NFA is known as a UFA (U stands for Unique).