I am confused about the usage of "Ø" in the DFA / NFA ( Let's talk about this in the context of DFA to NFA conversion )
Let's say that I have a NFA as follows: enter image description here
There isn't any transition defined for symbol "a" for state 1. So in the transition table would i write the transition for the same as "Ø" or do i write "1" cause it will stay in state "1" as there isn't any transition arrow for it
So would it be this:
| state | a | b | E |
|----------------|----------|-------|---------|
| 1 | Ø | {2} | {3} |
| 2 | {2,3} | {3} | Ø |
| 3 | {1} | Ø | Ø |
or:
| state | a | b | E |
|----------------|----------|-------|---------|
| 1 | {1} | {2} | {3} |
| 2 | {2,3} | {3} | {2} |
| 3 | {1} | {3} | {3} |
The choice to use "Ø" affects the final output. Now, we could construct the power set of the states and then calcualte epsilon clousure, but let's cut it short, we will directly Let's look at a controversial state that may or may not be present in the final DFA, and we will try experiment using "Ø" and not using "Ø"
(1) Not using null: ( Table 2 )
State = {1,2}
From 1 and 2, on receiving a we go to 1,2,3
epsilon closure (1,2,3) = 1,2,3
(2) Using null: ( Table 1 )
State = {1,2}
From 1 and 2, on receiving a we go to {2,3}
epsilon closure (2,3) = 1,2,3
Now, the transition might look same but in some cases we would end up again with states where we don't have anywhere to go but to stay in the same state and if we choose to use "Ø" then we would have an additional state in the final output "Ø". In this case, it just means that if we don't have a transition for some symbol then we go to this state
But if we don't then our final output won't have the extra state "Ø". Here we don't specify the transition arrow for some symbol if we don't a transition for it, just like as for symbol "a" in state 1, in the diagram
So, which one is correct, one without the state "Ø" or one with the state "Ø"
The one with Ø. Consider a simple NFA:
/-> S -a-> (T)
| |
\-a-/
S is the start state, T is an accepting state. The alphabet is {a, b}.
When this machine reads the string b, it rejects. If the transition set for (S, b) were {S}, then the DFA this converts into would accept ba, which is obviously wrong.
The right transition states are as follows:
S, a, {S, T}
S, b, Ø
{S, T}, a, {S, T}
{S, T}, b, Ø
Ø, a, Ø
Ø, b, Ø
And you could draw this DFA in two ways. A incomplete DFA (where the null state is omitted) or a complete DFA (where the null state is present as an inescapable state). q1 = {S}, the start state, and q2 = {S, T}, the accepting state.
Incomplete:
q1 -a-> (q2)<-\
| |
\-a-/
Complete:
/a,b\
| /
\ v
/-> q3 <-\
b b
| |
q1 -a-> (q2)<-\
| |
\-a-/
Note that in the complete version, q3 has the same properties as Ø.
(In general an incomplete DFA can always be replaced with a complete DFA in this manner: create a new non-accepting state d, whose outgoing transitions are d, Σ, d, and whose incoming transitions are whatever transitions are missing from the original DFA. d is the "dump" state, and can be thought of as a "rejecting" state as opposed to an accepting state. As soon as an input leads into that state, it has no path to acceptance and so can be rejected.)