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

[evinda]

Hello! (Wave)

I want to construct a dfa that recognizes the language $((0 \cup 1)^{\ast} 1 0^{\ast}) \cup 0$.

I have thought of the following NFA:

View attachment 5833

But I am facing difficulties on converting this to a NFA. Could you give me a hint how we could do this?

 

[I like Serena]

Hello! (Wave)

I want to construct a dfa that recognizes the language $((0 \cup 1)^{\ast} 1 0^{\ast}) \cup 0$.

I have thought of the following NFA:
But I am facing difficulties on converting this to a NFA. Could you give me a hint how we could do this?

Hey evinda! (Smile)

Once we've started recognizing $(0 \cup 1)^{\ast}$, we're too late to match the $0$ at the end.
As it is now we might match for instance $00$, which is not supposed to be accepted.

So I think we need to split the first state into 2 states, and put a new start state before them.
One for the $(0 \cup 1)^{\ast}$ part, and another for the $0$-at-the-end part. (Sweating)

 

[evinda]

Hey evinda! (Smile)

Once we've started recognizing $(0 \cup 1)^{\ast}$, we're too late to match the $0$ at the end.
As it is now we might match for instance $00$, which is not supposed to be accepted.

So I think we need to split the first state into 2 states, and put a new start state before them.
One for the $(0 \cup 1)^{\ast}$ part, and another for the $0$-at-the-end part. (Sweating)

So you mean that the following nfa would recognize the language?

View attachment 5834

 

[I like Serena]

So you mean that the following nfa would recognize the language?

Yep. (Nod)

 

[evinda]

Yep. (Nod)

And how can we convert this to a dfa?

 

[I like Serena]

And how can we convert this to a dfa?

How about following the procedure to make such a conversion? (Wondering)

 

[I like Serena]

We should label each of the states with, say, $q_0, q_1, q_2, q_3$.
Then we'll create new states, starting with the starting state.
From there we need to create a new state that is associated with the set of states we can reach when we read $0$.
And another state that is associated with the set of states we can reach when we read $1$.
After that we should repeat until we have our DFA. (Nerd)

So the first new state is $Q_0=\{q_0\}$.
From there we get $Q_1=\{q_1, q_3\}$ that we can reach with $0$.
And $Q_2=\{q_1, q_2\}$ that we can reach with $1$. (Thinking)

 

[evinda]

We should label each of the states with, say, $q_0, q_1, q_2, q_3$.
Then we'll create new states, starting with the starting state.
From there we need to create a new state that is associated with the set of states we can reach when we read $0$.
And another state that is associated with the set of states we can reach when we read $1$.
After that we should repeat until we have our DFA. (Nerd)

So the first new state is $Q_0=\{q_0\}$.
From there we get $Q_1=\{q_1, q_3\}$ that we can reach with $0$.
And $Q_2=\{q_1, q_2\}$ that we can reach with $1$. (Thinking)

We can reach $q_2$ after having read $\epsilon, 0 \text{ or } 1$ and $1$.
Why is it included at $Q_2$ ? So doesn't it contain all the states that could be reached after having read once $1$ ?

Then, do we set as $Q_3$ the set of states that can be reached from $q_1$ or $q_3$ by reading 0 and as $Q_4$ the set of states that can be reached from $q_1$ or $q_2$ by reading 1?

Or have I understood it wrong? (Thinking)

 

[I like Serena]

We can reach $q_2$ after having read $\epsilon, 0 \text{ or } 1$ and $1$.
Why is it included at $Q_2$ ? So doesn't it contain all the states that could be reached after having read once $1$ ?

We can also reach $q_2$ after $\epsilon, 1$, without reading a $0$ or $1$ in between. (Thinking)

Then, do we set as $Q_3$ the set of states that can be reached from $q_1$ or $q_3$ by reading 0 and as $Q_4$ the set of states that can be reached from $q_1$ or $q_2$ by reading 1?

Or have I understood it wrong? (Thinking)

First off, $Q_2$ should be a final state, since we can stop there.
And indeed, $Q_3$ would be the state after reading $0$ from $Q_1$ representing $q_1$ or $q_3$.
Logically $Q_4$ would be the state after reading $1$ from $Q_1$ representing $q_1$ or $q_3$.
And $Q_5, Q_6$ after reading $0$ respectively $1$ from $Q_2$ representing $q_1$ or $q_2$.

When we define $Q_2,Q_3,Q_4,Q_5$, we can see if we can merge some of them without losing anything. (Thinking)

 

[evinda]

We can also reach $q_2$ after $\epsilon, 1$, without reading a $0$ or $1$ in between. (Thinking)

Oh yes, that's right... (Smile)

First off, $Q_2$ should be a final state, since we can stop there.
And indeed, $Q_3$ would be the state after reading $0$ from $Q_1$ representing $q_1$ or $q_3$.
Logically $Q_4$ would be the state after reading $1$ from $Q_1$ representing $q_1$ or $q_3$.
And $Q_5, Q_6$ after reading $0$ respectively $1$ from $Q_2$ representing $q_1$ or $q_2$.

When we define $Q_2,Q_3,Q_4,Q_5$, we can see if we can merge some of them without losing anything. (Thinking)

So we have the following, right?

$$Q_0=\{q_0\} \\ Q_1=\{ q_1, q_3\} \\ Q_2=\{ q_1, q_2\} \\ Q_3= \{ q_1 \} \\ Q_4=\{ q_1, q_2\} \\ Q_5=\{ q_1, q_2\} \\ Q_6=\{ q_1, q_2\}$$

How can we check if we can merge some of the states without losing anything? (Thinking)

 

[I like Serena]

Oh yes, that's right... (Smile)

So we have the following, right?

$$Q_0=\{q_0\} \\ Q_1=\{ q_1, q_3\} \\ Q_2=\{ q_1, q_2\} \\ Q_3= \{ q_1 \} \\ Q_4=\{ q_1, q_2\} \\ Q_5=\{ q_1, q_2\} \\ Q_6=\{ q_1, q_2\}$$

How can we check if we can merge some of the states without losing anything? (Thinking)

Yep. (Nod)

Additionally, $Q_1, Q_2, Q_4, Q_5, Q_6$ are all states where we can stop - final states.
But $Q_3$ is not a final state.

$Q_4, Q_5, Q_6$ are completely identical to $Q_2$.
That is, the all refer to the same set of states $\{q_1, q_2\}$, and they are all final states.
So we can remove them and redirect the arrows pointing to them to $Q_2$. (Thinking)

Now where can we go from $Q_3$? (Wondering)

 

[evinda]

Yep. (Nod)

Additionally, $Q_1, Q_2, Q_4, Q_5, Q_6$ are all states where we can stop - final states.
But $Q_3$ is not a final state.

$Q_4, Q_5, Q_6$ are completely identical to $Q_2$.
That is, the all refer to the same set of states $\{q_1, q_2\}$, and they are all final states.
So we can remove them and redirect the arrows pointing to them to $Q_2$. (Thinking)

Now where can we go from $Q_3$? (Wondering)

By reading $0$ we can go to $\{q_1\}$ and by reading $1$ we go to $Q_2$, right? (Thinking)

 

[I like Serena]

By reading $0$ we can go to $\{q_1\}$ and by reading $1$ we go to $Q_2$, right? (Thinking)

Reading $0$ brings us indeed back to $Q_3=\{q_1\}$. (Nod)

Doesn't reading $1$ bring us to a new state $\{q_2\}$? (Wondering)

 

[evinda]

Doesn't reading $1$ bring us to a new state $\{q_2\}$? (Wondering)

Could you explain to me why? Can't we go from $q_1$ to $q_1$ by reading 1?

 

[I like Serena]

Could you explain to me why? Can't we go from $q_1$ to $q_1$ by reading 1?

My mistake. You were right. Reading $1$ in $\{q_1\}$ brings us to $\{q_1,q_2\}$. (Blush)

 

[evinda]

My mistake. You were right. Reading $1$ in $\{q_1\}$ brings us to $\{q_1,q_2\}$. (Blush)

(Smile)

So now will we continue with the same procedure? With which criterion do we stop? (Thinking)

 

[I like Serena]

(Smile)

So now will we continue with the same procedure? With which criterion do we stop? (Thinking)

Yep. We stop if we can't get to new states any more. (Wink)

 

[I like Serena]

I think we have the following diagrams now, don't we?

The original NFA we found for $((0∪1)^∗10^∗)∪0$ is:
View attachment 5879

And we got to the DFA:
View attachment 5878

Right? (Wondering)

 

[evinda]

I think we have the following diagrams now, don't we?

The original NFA is:And we got to the DFA:Right? (Wondering)

Yes, right... (Nod)

Yep. We stop if we can't get to new states any more. (Wink)

What do you mean? If we have found all the possible subsets of the set of the initial states? (Thinking)

 

[I like Serena]

What do you mean? If we have found all the possible subsets of the set of the initial states? (Thinking)

That's not necessary.
Any of the other possible subsets are not reachable from the start state.
So there is no point to add them to the DFA.

Does the DFA we have now correspond to the language $((0∪1)^∗10^∗)∪0$? (Wondering)

 

[evinda]

That's not necessary.
Any of the other possible subsets are not reachable from the start state.
So there is no point to add them to the DFA.

So do we write some of the states arbitrarily and check if these recognize the language and otherwise we continue the procedure we were talking about before? Or have I understood it wrong? (Sweating)

Does the DFA we have now correspond to the language $((0∪1)^∗10^∗)∪0$? (Wondering)

No, it doesn't. After having read for example $1^{\ast}$ we don't reach necessarily 1. Also I noticed that it doesn't recognize the word 0.

 

[I like Serena]

So do we write some of the states arbitrarily and check if these recognize the language and otherwise we continue the procedure we were talking about before? Or have I understood it wrong? (Sweating)

Not really.
We begin at the start state and we add new states representing the sets of states that can be reached by $0$ respectively $1$. When the only states we can go to are already there, we're done. (Whew)

No, it doesn't. After having read for example $1^{\ast}$ we cannot reach 1. Also I noticed that it doesn't recognize the word 0.

Huh?

What do you mean that we "cannot reach $1$"?
Which word with $1^{\ast}$ can we not recognize?

Isn't $0$ recognized with $\{q_0\} \overset{0}\to \{q_1,q_3\}$ after which we can stop, since we're in a final state? (Wondering)

 

[evinda]

Not really.
We begin at the start state and we add new states representing the sets of states that can be reached by $0$ respectively $1$. When the only states we can go to are already there, we're done. (Whew)

How do we know which are the only states where we can go? (Thinking)

Huh?

What do you mean that we "cannot reach $1$"?
Which word with $1^{\ast}$ can we not recognize?

Isn't $0$ recognized with $\{q_0\} \overset{0}\to \{q_1,q_3\}$ after which we can stop, since we're in a final state? (Wondering)

Oh yes, you are right! The automaton recognizes the language $((0 \cup 1)^{\ast}10^{\ast}) \cup 0$... (Blush)

 

[I like Serena]

How do we know which are the only states where we can go? (Thinking)

I don't understand your question.

Didn't we check at every step what the full set of states was that we could go to from any of the state-sets we had for every input symbol?

 

[evinda]

I don't understand your question.

Didn't we check at every step what the full set of states was that we could go to from any of the state-sets we had for every input symbol?

In this case, we do not have a transition function for the desired dfa.
I haven't understood when we can't get to new states... (Worried)

 

[I like Serena]

In this case, we do not have a transition function for the desired dfa.
I haven't understood when we can't get to new states... (Worried)

Sure we do. We've been building the transition function.
Can you list it?

 

[evinda]

Sure we do. We've been building the transition function.
Can you list it?

Don't we have the following transition function for our initial nfa? Or am I wrong? (Thinking)

$\delta: \begin{matrix}
& 0 & 1 &\epsilon\\
q_0 & \{q_1,q_3\} & \{q_1\} & \{q_1\}\\
q_1 & \{q_1\} & \{q_1, q_2\}& \varnothing\\
q_2 & \{q_2\} & \varnothing& \varnothing\\
q_3 & \varnothing & \varnothing& \varnothing
\end{matrix}$

 

[I like Serena]

Don't we have the following transition function for our initial nfa? Or am I wrong? (Thinking)

$\delta: \begin{matrix}
& 0 & 1 &\epsilon\\
q_0 & \{q_1,q_3\} & \{q_1\} & \{q_1\}\\
q_1 & \{q_1\} & \{q_1, q_2\}& \varnothing\\
q_2 & \{q_2\} & \varnothing& \varnothing\\
q_3 & \varnothing & \varnothing& \varnothing
\end{matrix}$

I think we should have $\delta(q_0,0)=\{q_3\}$ and $\delta(q_0,1)=\varnothing$. (Thinking)
Otherwise it's correct.

 

[evinda]

I think we should have $\delta(q_0,0)=\{q_3\}$ and $\delta(q_0,1)=\varnothing$. (Thinking)
Otherwise it's correct.

A ok. And in order to use the known procedure do we have to add new states and get rid of the $\epsilon$-transition?
Or am I wrong? (Sweating)

 

[I like Serena]

A ok. And in order to use the known procedure do we have to add new states and get rid of the $\epsilon$-transition?
Or am I wrong? (Sweating)

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)

 

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