Return to Answer

There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

• In the forward closure, you are trying to apply $\varepsilon$-transitions after each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problème for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.
• In the backward closure, you are trying to apply $\varepsilon$-transitions before each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\}$ and $\Delta''(q, a) = \bigcup\limits_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied, unless $I = \{q_0\}$ and $\mathcal{E}(q_0) = \{q_0\}$.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^*b^*c^*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).

There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

• In the forward closure, you are trying to apply $\varepsilon$-transitions after each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problem for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.
• In the backward closure, you are trying to apply $\varepsilon$-transitions before each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\}$ and $\Delta''(q, a) = \bigcup\limits_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied, unless $I = \{q_0\}$ and $\mathcal{E}(q_0) = \{q_0\}$.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^*b^*c^*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).

There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

• In the forward closure, you are trying to apply $\varepsilon$-transitions after each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problème for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.
• In the backward closure, you are trying to apply $\varepsilon$-transitions before each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\}$ and $\Delta''(q, a) = \bigcup\limits_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^*b^*c^*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).

There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

• In the forward closure, you are trying to apply $\varepsilon$-transitions after each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problème for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.
• In the backward closure, you are trying to apply $\varepsilon$-transitions before each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\}$ and $\Delta''(q, a) = \bigcup\limits_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied, unless $I = \{q_0\}$ and $\mathcal{E}(q_0) = \{q_0\}$.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^*b^*c^*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).

There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

• In the forward closure, you are trying to apply $\varepsilon$-transitions after each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problème for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.
• In the backward closure, you are trying to apply $\varepsilon$-transitions before each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\}$ and $\Delta''(q, a) = \bigcup\limits_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^*b^*c^*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).

There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

• In the forward closure, you are trying to apply $\varepsilon$-transitions after each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problème for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.
• In the backward closure, you are trying to apply $\varepsilon$-transitions before each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\}$ and $\Delta''(q, a) = \bigcup\limits_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^*b^*c^*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).