0
$\begingroup$

I am at a loss here on this problem I have been working on for some time. It first starts out by asking for me to find a Deterministic Finite Automaton (DFA) for the following language:

Language

I then deduced that the DFA would have to be as follows:

DFA

The problem then continues on by asking me to find a Nondeterministic Finite Automata (NFA) that represents the same language. However, I don't believe there is a simpler answer, that by adding nondeterminism would yield a simpler and non-forced answer. Correct me if I am wrong, but the biggest problem here is that we start in the final state to begin with and so there is no way to roll that into an NFA without have the identical edges as in the DFA.

Am I missing something? Would the answer for the DFA be the same for the NFA as well? If not, what would be the deduced NFA that could exploit the nondeterminism to create a simpler answer?

$\endgroup$
2
$\begingroup$

The language $L$ has three distinct language quotients, corresponding to languages accepted from the three states of the minimal DFA:

$$\begin{align} (\Sigma^*bb)^{-1} L &= \{\, w \mid bbw \in L\,\} = L \setminus \{\, \epsilon, b \,\} \\ (\epsilon \cup \Sigma^*a)^{-1} L &= \{\, w \mid aw \in L\,\} = L \\ (b \cup \Sigma^*ab)^{-1}L &= \{\, w \mid abw \in L\,\} = L \setminus \{\, b\,\} \enspace, \end{align}$$

where $\Sigma = \{\,a,b\,\}$. A DFA must have at least one state per distinct quotient (exactly one if the DFA is minimal). In general, an NFA may have fewer states than quotients, because a quotient may equal the union of languages accepted from multiple states.

However, in this case it's not possible to go below three states, because there must be two distinct accepting states and one non-accepting state. In fact, both $(\epsilon \cup \Sigma^*a)$ and $(b \cup \Sigma^*ab)$ are subsets of $L$, but have distinct quotients and cannot be merged.

The non-accepting state is necessary because the quotient of $(\Sigma^*bb)$ is nonempty. Hence there must be a non-accepting state with a path to accepting states.

Once you fix the three states, you also fix the languages accepted from them. This means that in this case all transitions in the DFA are essential. We can add some redundancy, though. Observe that

$$ L \setminus \{\,\epsilon,b\,\} \subseteq L \setminus \{\,b\,\} \subseteq L \enspace. $$

If there is a transition on input $\sigma$ from $q$ to $q'$, we can freely add a transition from $q$ to $q''$ for the same input as long as the language accepted from $q''$ is a subset of the language accepted from $q'$.

For example, we can add a transition labeled $b$ from $q_0$ to $q_2$. Of course, if we count states and transitions, our automaton hasn't gotten any simpler.

$\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.