2
$\begingroup$

I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition.

But I want to know how can I do so without epsilon transition

Here's my idea

  1. Suppose s1 and s2 are the start states. Let s0 be the new start state.
  2. If s1 or s2 are final states, make s0 final state.
  3. Duplicate all outgoing-edges (transitions) from s1 and s2 to s0 without changing edge labels.
  4. s1 and s2 are no longer start states.

I feel my idea should work, but I just wanted a confirmation.

$\endgroup$
2
  • 1
    $\begingroup$ A quick search would've shown that there is a standard technique for getting rid of $\epsilon$-transitions. Combine it with the one you already know for turning an NFA with multiple initial states into an $\epsilon$-NFA with a unique initial state. When you're proposing a "new" technique you should at least try to prove it correct yourself before enlisting help on a site like this. $\endgroup$
    – Kai
    Sep 4, 2023 at 5:11
  • $\begingroup$ I never said it's a new technique. It's a pretty standard thing when removing epsilon transitions. Problem is, some sources says s1 and s2 should become start states when you remove epsilon transitions, which means our NFA will again have multiple start states. It kinda confused me. Can you prove not making s1 and s2 start state after removing epsilon transitions will give me incorrect NFA? $\endgroup$
    – Archaic
    Sep 7, 2023 at 15:30

1 Answer 1

1
$\begingroup$

You got the right intuition. Here is how to do it formally:

Removing $\epsilon$-transitions is standard and easy to do. Lets say that the resulted NFA $A = \langle \Sigma, Q, Q_0, \delta, F\rangle$ that you get has more than one initial state, that is $|Q_0| > 1$. In this case, you can modify $A$ to get an equivalent automaton with a single initial state, simply by adding one more state, and without using $\epsilon$-transitions:

Define the NFA $B = \langle \Sigma, Q\cup \{q_{new}\}, \{q_{new}\}, \eta, F\cup \{ q_{new}: Q_0\cap F\neq \emptyset\}\rangle$, where $q_{new}\notin Q$ , and for every letter $a\in \Sigma$ and state $q\in Q$, it holds that:

1- $\eta(q_{new}, \sigma) = \bigcup\limits_{q\in Q_0} \delta(q, \sigma)$.

2 - $\eta(q, \sigma) = \delta(q, \sigma)$.

So essentially $B$ is obtained from A by adding a new state $q_{new}$, which is the only initial state of $B$. Upon reading $\sigma$ from $q_{new}$ we move nondeterministically to any state that we can reach in $A$ from $Q_0$ upon reading $\sigma$, and finally $q_{new}$ is considered accepting only when there is an initial state in $A$ that is accepting (this part handles the empty-word $\epsilon$).

Correctness follows easily. I leave the empty-word case for you, and simply note that once $B$ leaves the state ${q_{new}}$, it cannot go back to it, and has to proceed by following transitions of $A$. Now every accepting run of $A$ can be replaced by an accepting run of $B$ -- you only have to replace the initial state of the run with $q_{new}$, and then verify that the resulted run is legal in B and accepting. Conversely, every accepting run $r$ of $B$ on a non-empty word has a corresponding accepting run of A on the same word: if $q_{new} \xrightarrow{a} q$ is the first transition that $r$ traverses, then by definition, there is some $q_0\in Q_0$ such that $q\in \delta(q_0, a)$ and thus we can replace the transition $q_{new} \xrightarrow{a} q$ with $q_0 \xrightarrow{a} q$ to get an accepting run of $A$.

So what you should do first is define formally the automaton that you think works, and then try to prove that it is indeed equivalent. I leave the details to you.

Note that what I actually did is removal of $\epsilon$-transitions -- it can be done in several ways, but if you care about a single initial state, that can also be done, as we showed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.