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

[evinda]

I don't think so.
We can convert it to states with sets of the original states.
For $\epsilon$-transitions, we just need to draw in additional states that might be reached with an $\epsilon$-transition. (Thinking)

I haven't really understood what we have to do... (Worried)

By ignoring the $\epsilon$-transition, we have the following. Right?

$\begin{matrix}
& 0 & 1\\
\{q_0\} & \{q_3\} &\varnothing \\
\{q_3\} & \varnothing & \varnothing
\end{matrix}$

By including the $\epsilon$-transition, we have the following additional transitions:

$q_0 \overset{0,1}{\to} q_1$ and $q_0 \overset{1}{\to} q_3$

So do we have the following transition function?

$\begin{matrix}
& 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_3\} \\
\{q_3\} & \varnothing & \varnothing
\end{matrix}$Or have I understood it wrong? (Sweating)

 

[I like Serena]

I haven't really understood what we have to do... (Worried)

By ignoring the $\epsilon$-transition, we have the following. Right?

$\begin{matrix}
& 0 & 1\\
\{q_0\} & \{q_3\} &\varnothing \\
\{q_3\} & \varnothing & \varnothing
\end{matrix}$

By including the $\epsilon$-transition, we have the following additional transitions:

$q_0 \overset{0,1}{\to} q_1$ and $q_0 \overset{1}{\to} q_3$

So do we have the following transition function?

$\begin{matrix}
& 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_3\} \\
\{q_3\} & \varnothing & \varnothing
\end{matrix}$Or have I understood it wrong? (Sweating)

Shouldn't that be:
$q_0 \overset{0,1}{\to} q_1$ and $q_0 \overset{1}{\to} q_2$? (Wondering)Not so fast. (Worried)
Let's start with:
$\begin{matrix}
\delta' & 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_2\}
\end{matrix}$

Now we've found 2 new states, and we should try and find out where we can go from them, including implicit $\epsilon$-transitions if there are any:
$\begin{matrix}
\delta' & 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_2\} \\
\{q_1,q_3\} & ? & ? \\
\{q_1,q_2\} & ? & ?
\end{matrix}$

(Thinking)

 

[evinda]

Shouldn't that be:
$q_0 \overset{0,1}{\to} q_1$ and $q_0 \overset{1}{\to} q_2$? (Wondering)

Oh yes, right... (Blush)

Not so fast. (Worried)
Let's start with:
$\begin{matrix}
\delta' & 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_2\}
\end{matrix}$

Now we've found 2 new states, and we should try and find out where we can go from them, including implicit $\epsilon$-transitions if there are any:
$\begin{matrix}
\delta' & 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_2\} \\
\{q_1,q_3\} & ? & ? \\
\{q_1,q_2\} & ? & ?
\end{matrix}$

(Thinking)

So we have the following transition function, right?$\begin{matrix}
\delta' & 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_2\} \\
\{q_1,q_3\} & \{ q_1\} & \{ q_1, q_2\} \\
\{q_1,q_2\} & \{q_1,q_2\} & \{ q_1, q_2\} \\
\{q_1\} & \{ q_1\} & \{ q_1, q_2 \}
\end{matrix}$

And these are all the states that are reachable from the starting state. So we get the following dfa

View attachment 5889

which is the same as we found before, right? (Smile)

 

[I like Serena]

Oh yes, right... (Blush)
So we have the following transition function, right?$\begin{matrix}
\delta' & 0 & 1\\
\{q_0\} & \{q_1,q_3\} &\{q_1, q_2\} \\
\{q_1,q_3\} & \{ q_1\} & \{ q_1, q_2\} \\
\{q_1,q_2\} & \{q_1,q_2\} & \{ q_1, q_2\} \\
\{q_1\} & \{ q_1\} & \{ q_1, q_2 \}
\end{matrix}$

And these are all the states that are reachable from the starting state. So we get the following dfa
which is the same as we found before, right? (Smile)

Yep! (Nod)

One observation, according to your notes:

http://mathhelpboards.com/attachments/discrete-mathematics-set-theory-logic-15/5765d1469112227-construction-dfa-pr22-jpg

the start state should be $\{q_0, q_1\}$ instead of $\{q_0\}$, although that doesn't really change the DFA. (Nerd)

 

[evinda]

the start state should be $\{q_0, q_1\}$ instead of $\{q_0\}$, although that doesn't really change the DFA. (Nerd)

Why is it like that? (Thinking)

 

[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)