Find DFA Equiv: States, Transitions & Function

[evinda]

Hello! (Wave)

I want to find a DFA equivalent with the following:

View attachment 5867

Do we have to follow the following procedure?

View attachment 5868

If so do we have to find the transition function having the following states?

$$\{A\} , \{ B \}, \{ C \}, \{ A,B \}, \{ A,C \}, \{ B,C \}, \{A,B,C\}$$

 

[I like Serena]

Hello! (Wave)

I want to find a DFA equivalent with the following:
Do we have to follow the following procedure?
If so do we have to find the transition function having the following states?

$$\{A\} , \{ B \}, \{ C \}, \{ A,B \}, \{ A,C \}, \{ B,C \}, \{A,B,C\}$$

Hey evinda! (Smile)

Yep, except that we should include $\varnothing$ as well. (Nerd)

 

[evinda]

I found the following transition function:

$$\delta': \begin{matrix}
& 0 & 1\\
\{A\} & \{A\} & \varnothing \\
\{B\} & \varnothing & \{C\}\\
\{C\} & \varnothing & \{B\}\\
\{A,B\} & \{A\} & \{C\}\\
\{A,C\} & \{A\} &\{B\} \\
\{B,C\} & \varnothing & \{B,C\}\\
\{A,B,C\} & \{A\} & \{B,C\}\\
\varnothing & \varnothing & \varnothing
\end{matrix}$$So the dfa will look as follows, right? (Thinking)View attachment 5872

 

[I like Serena]

I found the following transition function:

$$\delta': \begin{matrix}
& 0 & 1\\
\{A\} & \{A\} & \varnothing \\
\{B\} & \varnothing & \{C\}\\
\{C\} & \varnothing & \{B\}\\
\{A,B\} & \{A\} & \{C\}\\
\{A,C\} & \{A\} &\{B\} \\
\{B,C\} & \varnothing & \{B,C\}\\
\{A,B,C\} & \{A\} & \{B,C\}\\
\varnothing & \varnothing & \varnothing
\end{matrix}$$So the dfa will look as follows, right? (Thinking)

Hmm... the start state is missing... shouldn't we start with $q_0'=\{A\}$ as start state (rule 3)? (Wondering)

According to rule 2, shouldn't we have:
$$\delta'(q_0', 0) = \delta'(\{A\}, 0) = \bigcup_{r \in \{A\}} \delta(r, 0) = \delta(A,0) = \{A,B,C\}$$
(Wondering)

 

[evinda]

Hmm... the start state is missing... shouldn't we start with $q_0'=\{A\}$ as start state (rule 3)? (Wondering)

According to rule 2, shouldn't we have:
$$\delta'(q_0', 0) = \delta'(\{A\}, 0) = \bigcup_{r \in \{A\}} \delta(r, 0) = \delta(A,0) = \{A,B,C\}$$
(Wondering)

Oh yes, that's right! (Nod) Is everything else correct?

 

[I like Serena]

Oh yes, that's right! (Nod) Is everything else correct?

Well... we have indeed $\delta'(\{A\}, 1)=\varnothing$. (Nod)

But what should $\delta'(\{A,B,C\}, 0)$ be?
And $\delta'(\{A,B,C\}, 1)$? (Wondering)

 

[evinda]

Well... we have indeed $\delta'(\{A\}, 1)=\varnothing$. (Nod)

But what should $\delta'(\{A,B,C\}, 0)$ be?

$\{A,B,C \}$

And $\delta'(\{A,B,C\}, 1)$? (Wondering)

$\{B,C\}$

Right?

 

[I like Serena]

$\{A,B,C \}$

$\{B,C\}$

Right?

Right.

And isn't $\delta'(\{A,B\}, 0) = \{A,B\}$ and $\delta'(\{A,C\}, 0) = \{A,C\}$? (Wondering)

 

[evinda]

Right.

And isn't $\delta'(\{A,B\}, 0) = \{A,B\}$ and $\delta'(\{A,C\}, 0) = \{A,C\}$? (Wondering)

Isn't it $\delta'(\{A,B\}, 0) = \{A,B, C\}$ and $\delta'(\{A,C\}, 0) = \{A,B, C\}$ because of the transitions from A to C by reading 0 and from A to B by reading 0 respectively? Or am I wrong?

 

[I like Serena]

Isn't it $\delta'(\{A,B\}, 0) = \{A,B, C\}$ and $\delta'(\{A,C\}, 0) = \{A,B, C\}$ because of the transitions from A to C by reading 0 and from A to B by reading 0 respectively? Or am I wrong?

Oh yes. You are right! (Blush)

 

[evinda]

So we get the following dfa, right?

View attachment 5880

 

[I like Serena]

So we get the following dfa, right?

I think there are 2 arrows missing from $\{A,B,C\}$... (Thinking)

Btw, did you notice that 4 of those 8 states are not reachable from the start state? (Wondering)

 

[evinda]

I think there are 2 arrows missing from $\{A,B,C\}$... (Thinking)

Oh yes, right... I forgot to write the transition from $\{A,B,C\}$ to $\{A,B,C\}$ by reading 0, and the transition from $\{A,B,C\}$ to $\{B,C\}$ by reading 1.

So the dfa is the following:

View attachment 5881

Btw, did you notice that 4 of those 8 states are not reachable from the start state? (Wondering)

Yes, the states $\{ B \}, \{C\}, \{A,B\}, \{A,C\}$.
But all the states of a dfa should be reachable from the start state, right? (Thinking)

 

[I like Serena]

Oh yes, right... I forgot to write the transition from $\{A,B,C\}$ to $\{A,B,C\}$ by reading 0, and the transition from $\{A,B,C\}$ to $\{B,C\}$ by reading 1.

So the dfa is the following:

Yep. (Nod)

Yes, the states $\{ B \}, \{C\}, \{A,B\}, \{A,C\}$.
But all the states of a dfa should be reachable from the start state, right? (Thinking)

Does the definition require that?
Last time I checked we can have unreachable states - it's just that we might as well leave them out.
They're just making the diagram messier than it needs to be. (Emo)
Anyway, the procedure you quoted did include all of them.
That is, it specifically said that the set of states would be $q'=\mathcal P(q)$.

 

[evinda]

Last time I checked we can have unreachable states - it's just that we might as well leave them out.
They're just making the diagram messier than it needs to be. (Emo)

So a dfa equivalent to the given initial nfa is the following, right?View attachment 5882

In order to know which states are reachable from the starting state do we look at the states where we can go from the states where the starting state can go? (Blush)

I.e. in this case, we have

$\begin{matrix}
& 0 & 1\\
\{A\} &\{A,B,C\} & \varnothing
\end{matrix}$

and

$\begin{matrix}
& 0 & 1\\
\{A,B,C\} &\{A,B,C\} & \{B,C\}
\end{matrix}$

so we deduce that we have to include at the dfa the states $\{A\}, \{A,B,C\}$ and $\{B,C \}$, right? (Thinking)

 

[I like Serena]

So a dfa equivalent to the given initial nfa is the following, right?

In order to know which states are reachable from the starting state do we look at the states where we can go from the states where the starting state can go? (Blush)

I.e. in this case, we have

$\begin{matrix}
& 0 & 1\\
\{A\} &\{A,B,C\} & \varnothing
\end{matrix}$

and

$\begin{matrix}
& 0 & 1\\
\{A,B,C\} &\{A,B,C\} & \{B,C\}
\end{matrix}$

so we deduce that we have to include at the dfa the states $\{A\}, \{A,B,C\}$ and $\{B,C \}$, right? (Thinking)

Yep. (Nod)

That leaves only to check where we can go from $\{B,C \}$. (Sun)

 

[evinda]

Yep. (Nod)

That leaves only to check where we can go from $\{B,C \}$. (Sun)

I got it... Thanks a lot! (Smirk)