Finding DFA: Hint to Construct NFA for ((0∪1)*10* ∪ 0)

[I like Serena]

Why is it like that? (Thinking)

It's an arbitrary choice of the procedure.
It includes all empty transitions after each state.
Instead we just started with the start state after which we included all empty transitions before and after each state. (Nerd)

tl;dr it does not matter. (Wink)

 

[evinda]

It's an arbitrary choice of the procedure.
It includes all empty transitions after each state.
Instead we just started with the start state after which we included all empty transitions before and after each state. (Nerd)

tl;dr it does not matter. (Wink)

So it includes all the states we can reach after any $\epsilon$-transition? Or only the states we can reach after the $\epsilon$-transitions that are immediately reached from the starting state? (Thinking)

 

[I like Serena]

So it includes all the states we can reach after any $\epsilon$-transition? Or only the states we can reach after the $\epsilon$-transitions that are immediately reached from the starting state? (Thinking)

The $E$ function includes all states we can reach after any $\epsilon$-transition.
For consistency, no exception is made for the starting state. (Emo)

 

[evinda]

The $E$ function includes all states we can reach after any $\epsilon$-transition.

Which function do you mean with the "$E$ function" ? (Thinking)

 

[I like Serena]

Which function do you mean with the "$E$ function" ? (Thinking)

The one that your notes refer to as:

Formally, for $R \subseteq Q$ let
\[E(R)=\{q \mid q\text{ can be reached from R by traveling along $0$ or more $\varepsilon$ arrows} \}.\]
(Thinking)

 

[evinda]

The one that your notes refer to as:

Formally, for $R \subseteq Q$ let
\[E(R)=\{q \mid q\text{ can be reached from R by traveling along $0$ or more $\varepsilon$ arrows} \}.\]
(Thinking)

Yes, I see.. I had understood it wrong and I thought that you meant that the starting state should contain all the states that could be reached after any $\epsilon$-transition... but the new starting state contains the starting state of the nfa and any states that can be reached after having read $\epsilon$ exactly after the starting state. Right?

 

[I like Serena]

Yes, I see.. I had understood it wrong and I thought that you meant that the starting state should contain all the states that could be reached after any $\epsilon$-transition... but the new starting state contains the starting state of the nfa and any states that can be reached after having read $\epsilon$ exactly after the starting state. Right?

Yep! (Nod)

Still, that is any state that could be reached after any $\epsilon$-transition... without actually reading an input symbol. (Nerd)

 

[evinda]

Yep! (Nod)

Still, that is any state that could be reached after any $\epsilon$-transition... without actually reading an input symbol. (Nerd)

I see... Thank you! (Smile)

 

[evinda]

How can we justify in a few words that the dfa indeed recognizes the language $((0 \cup 1)^{\star}10^{\star}) \cup 0$? (Thinking)