# Thread: How to find the dfa

1. Hello!!!

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?

2. Originally Posted by evinda
Hello!!!

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!!

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.

3. Thread Author
Originally Posted by I like Serena
Hey evinda!!

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.
So you mean that the following nfa would recognize the language?

4. Originally Posted by evinda
So you mean that the following nfa would recognize the language?
Yep.

5. Thread Author
Originally Posted by I like Serena
Yep.
And how can we convert this to a dfa?

6. Originally Posted by evinda
And how can we convert this to a dfa?
How about following the procedure to make such a conversion?

7. 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.

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$.

8. Thread Author
Originally Posted by 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.

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$.
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?

9. Originally Posted by evinda
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.

Quote:
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?
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.

10. Thread Author
Originally Posted by I like Serena
We can also reach $q_2$ after $\epsilon, 1$, without reading a $0$ or $1$ in between.
Oh yes, that's right...

Originally Posted by I like Serena
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.

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?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•