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

Question

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.

Answer 1

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).

Every DFA is a UFA since every word has a unique path through the DFA (or, depending on your exact definition, at most one path). Some NFAs are UFAs, others are not.