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.
-
2$\begingroup$ What do you mean by "a grammar corresponds to an automaton"? $\endgroup$– Raphael ♦Jan 7, 2018 at 19:58
-
2$\begingroup$ Hint: A non-deterministic grammar can be unambiguous. $\endgroup$– Raphael ♦Jan 7, 2018 at 19:58
-
1$\begingroup$ Hint: There are infinitely many regular grammars (and automata) for every regular language -- some of them deterministic, some non-deterministic, and some ambiguous. $\endgroup$– Raphael ♦Jan 7, 2018 at 19:59
-
$\begingroup$ what i mean is we can draw a DFA or a NFA and convert it into right linear grammar (rlg) $\endgroup$– venkatJan 8, 2018 at 5:21
1 Answer
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.