equal
deleted
inserted
replaced
997 states of the NFA, that is in this case $\{0\}$. But in general there |
997 states of the NFA, that is in this case $\{0\}$. But in general there |
998 can of course be many starting states in the NFA and you would take |
998 can of course be many starting states in the NFA and you would take |
999 the corresponding subset as \emph{the} starting state of the DFA. |
999 the corresponding subset as \emph{the} starting state of the DFA. |
1000 |
1000 |
1001 The accepting states in the DFA are given by all sets that contain a |
1001 The accepting states in the DFA are given by all sets that contain a |
1002 $2$, which is the only accpting state in this NFA. But again in |
1002 $2$, which is the only accepting state in this NFA. But again in |
1003 general if the subset contains any accepting state from the NFA, then |
1003 general if the subset contains any accepting state from the NFA, then |
1004 the corresponding state in the DFA is accepting as well. This |
1004 the corresponding state in the DFA is accepting as well. This |
1005 completes the subset construction. The corresponding DFA for the NFA |
1005 completes the subset construction. The corresponding DFA for the NFA |
1006 shown above is: |
1006 shown above is: |
1007 |
1007 |
1055 from NFAs to DFAs exponentially increase, namely by $2^n$ (which is |
1055 from NFAs to DFAs exponentially increase, namely by $2^n$ (which is |
1056 the number of subsets you can form for sets of $n$ states). This blow |
1056 the number of subsets you can form for sets of $n$ states). This blow |
1057 up in the number of states in the DFA is again bad news for how |
1057 up in the number of states in the DFA is again bad news for how |
1058 quickly you can decide whether a string is accepted by a DFA or |
1058 quickly you can decide whether a string is accepted by a DFA or |
1059 not. So the caveat with DFAs is that they might make the task of |
1059 not. So the caveat with DFAs is that they might make the task of |
1060 finding the next state trival, but might require $2^n$ times as many |
1060 finding the next state trivial, but might require $2^n$ times as many |
1061 states then a NFA.\bigskip |
1061 states then a NFA.\bigskip |
1062 |
1062 |
1063 \noindent |
1063 \noindent |
1064 To conclude this section, how conveniently we can |
1064 To conclude this section, how conveniently we can |
1065 implement the subset construction with our versions of NFAs and |
1065 implement the subset construction with our versions of NFAs and |
1083 states are a set in the given NFA, but a single state in the DFA. The |
1083 states are a set in the given NFA, but a single state in the DFA. The |
1084 transition function, given the state \texttt{qs} and input \texttt{c}, |
1084 transition function, given the state \texttt{qs} and input \texttt{c}, |
1085 needs to produce the next state: this is the set of all NFA states |
1085 needs to produce the next state: this is the set of all NFA states |
1086 that are reachable from each state in \texttt{qs}. The function |
1086 that are reachable from each state in \texttt{qs}. The function |
1087 \texttt{nexts} from the NFA class already calculates this for us. The |
1087 \texttt{nexts} from the NFA class already calculates this for us. The |
1088 accepting-states function for the DFA is true henevner at least one |
1088 accepting-states function for the DFA is true whenever at least one |
1089 state in the subset is accepting (that is true) in the NFA.\medskip |
1089 state in the subset is accepting (that is true) in the NFA.\medskip |
1090 |
1090 |
1091 \noindent |
1091 \noindent |
1092 You might be able to spend some quality time tinkering with this code |
1092 You might be able to spend some quality time tinkering with this code |
1093 and time to ponder about it. Then you will probably notice that it is |
1093 and time to ponder about it. Then you will probably notice that it is |
1254 \end{tikzpicture} |
1254 \end{tikzpicture} |
1255 \end{center} |
1255 \end{center} |
1256 |
1256 |
1257 |
1257 |
1258 By the way, we are not bothering with implementing the above |
1258 By the way, we are not bothering with implementing the above |
1259 minimisation algorith: while up to now all the transformations used |
1259 minimisation algorithm: while up to now all the transformations used |
1260 some clever composition of functions, the minimisation algorithm |
1260 some clever composition of functions, the minimisation algorithm |
1261 cannot be implemented by just composing some functions. For this we |
1261 cannot be implemented by just composing some functions. For this we |
1262 would require a more concrete representation of the transition |
1262 would require a more concrete representation of the transition |
1263 function (like maps). If we did this, however, then many advantages of |
1263 function (like maps). If we did this, however, then many advantages of |
1264 the functions would be thrown away. So the compromise is to not being |
1264 the functions would be thrown away. So the compromise is to not being |