2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What do you mean by "a grammar corresponds to an automaton"? $\endgroup$ – Raphael Jan 7 '18 at 19:58
  • 2
    $\begingroup$ Hint: A non-deterministic grammar can be unambiguous. $\endgroup$ – Raphael Jan 7 '18 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 '18 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$ – venkat Jan 8 '18 at 5:21
3
$\begingroup$

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.

$\endgroup$

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.