Question

Say that an NFA is ambiguous if it accepts some string along two different computation branches

$\mathbf{Let}{\mathbf{AMBIG}}_{\mathrm{NFA}}\mathbf{=}\mathbf{\left\{}\mathbf{\left(}\mathbf{N}\mathbf{\right)}\mathbf{|}\mathbf{N}\mathbf{is}\mathbf{an}\mathbf{ambiguous}\mathbf{NFA}\mathbf{\right\}}\mathbf{.}$Show that${\mathbf{AMBIG}}_{\mathrm{NFA}}$ is decidable. (Suggestion: One elegant way to solve this problem is to construct a suitable DFA and then run ${\mathbf{E}}_{\mathrm{DFA}}$on it.)

Short answer

$AMBI{G}_{NFA}$is decidable.

Step-by-step solution

Explain NFA

The maximum number of various accepting paths that a nondeterministic finite automaton (NFA) M have for all the words in the language that it accepts is referred to as M's ambiguity.

Show that AMBIGNFA Decidable

The technique that follows determines $AMBI{G}_{NFA}$.To create a DFA D that replicates N and accepts a string if N accepts it along two distinct computational branches given an $NFAN.$ Then check whether D takes any strings using an EDFA decider. Our approach to creating D is comparable to the NFA-to-DFA conversion in Theorem. By leaving a pebble on each active state, imitate $N$.

Starting from the start state and moving along the transitions and place a red pebble on each state that is reached from the start state. The color of the pebbles is maintained by moving, adding, and removing them in accordance with N's transitions. Every time two or more pebbles are transferred to the same state, one of them for a blue pebble is swapped out. Following input reading, it is accepted if a blue pebble is on an accept state of $N$ or if red pebbles are present on two different accept states of $N$. There is a state in the$DFAD$ for each potential pebble position. There are three possible outcomes for each state of N: It may contain a red pebble, a blue pebble, or none at all. D therefore has 3 n states if $N$ has n states. To run the simulation, its start state, accept states, and transition functions are defined.

Hence ,$AMBI{G}_{NFA}$ is decidable.