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 |
1066 DFAs? Very conveninetly. The code is just: |
1066 DFAs? Very conveniently. The code is just: |
1067 |
1067 |
1068 {\small\begin{lstlisting}[language=Scala] |
1068 {\small\begin{lstlisting}[language=Scala] |
1069 def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { |
1069 def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { |
1070 DFA(nfa.starts, |
1070 DFA(nfa.starts, |
1071 { case (qs, c) => nfa.nexts(qs, c) }, |
1071 { case (qs, c) => nfa.nexts(qs, c) }, |
1271 reflect on what you have read so far, the story is that you can take a |
1271 reflect on what you have read so far, the story is that you can take a |
1272 regular expression, translate it via the Thompson Construction into an |
1272 regular expression, translate it via the Thompson Construction into an |
1273 $\epsilon$NFA, then translate it into a NFA by removing all |
1273 $\epsilon$NFA, then translate it into a NFA by removing all |
1274 $\epsilon$-transitions, and then via the subset construction obtain a |
1274 $\epsilon$-transitions, and then via the subset construction obtain a |
1275 DFA. In all steps we made sure the language, or which strings can be |
1275 DFA. In all steps we made sure the language, or which strings can be |
1276 recognised, stays the same. Of couse we should have proved this in |
1276 recognised, stays the same. Of cause we should have proved this in |
1277 each step, but let us cut corners here. After the last section, we |
1277 each step, but let us cut corners here. After the last section, we |
1278 can even minimise the DFA (maybe not in code). But again we made sure |
1278 can even minimise the DFA (maybe not in code). But again we made sure |
1279 the same language is recognised. You might be wondering: Can we go |
1279 the same language is recognised. You might be wondering: Can we go |
1280 into the other direction? Can we go from a DFA and obtain a regular |
1280 into the other direction? Can we go from a DFA and obtain a regular |
1281 expression that can recognise the same language as the DFA?\medskip |
1281 expression that can recognise the same language as the DFA?\medskip |
1343 \begin{eqnarray} |
1343 \begin{eqnarray} |
1344 Q_0 & = & \ONE + Q_0\,b + Q_0\,a\,b + Q_2\,b\\ |
1344 Q_0 & = & \ONE + Q_0\,b + Q_0\,a\,b + Q_2\,b\\ |
1345 Q_2 & = & Q_0\,a\,a + Q_2\,a |
1345 Q_2 & = & Q_0\,a\,a + Q_2\,a |
1346 \end{eqnarray} |
1346 \end{eqnarray} |
1347 |
1347 |
1348 \noindent where in Equation (4) we have two occurrences |
1348 \noindent where in Equation (6) we have two occurrences |
1349 of $Q_0$. Like the laws about $+$ and $\cdot$, we can simplify |
1349 of $Q_0$. Like the laws about $+$ and $\cdot$, we can simplify |
1350 Equation (4) to obtain the following two equations: |
1350 Equation (6) to obtain the following two equations: |
1351 |
1351 |
1352 \begin{eqnarray} |
1352 \begin{eqnarray} |
1353 Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\ |
1353 Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\ |
1354 Q_2 & = & Q_0\,a\,a + Q_2\,a |
1354 Q_2 & = & Q_0\,a\,a + Q_2\,a |
1355 \end{eqnarray} |
1355 \end{eqnarray} |
1466 |
1466 |
1467 \begin{quote} A language is \emph{regular} iff there exists an |
1467 \begin{quote} A language is \emph{regular} iff there exists an |
1468 automaton that recognises all its strings. |
1468 automaton that recognises all its strings. |
1469 \end{quote} |
1469 \end{quote} |
1470 |
1470 |
1471 \noindent Note that this is not a stement for a particular language |
1471 \noindent Note that this is not a statement for a particular language |
1472 (that is a particular set of strings), but about a large class of |
1472 (that is a particular set of strings), but about a large class of |
1473 languages, namely the regular ones. |
1473 languages, namely the regular ones. |
1474 |
1474 |
1475 As a consequence for deciding whether a string is recognised by a |
1475 As a consequence for deciding whether a string is recognised by a |
1476 regular expression, we could use our algorithm based on derivatives or |
1476 regular expression, we could use our algorithm based on derivatives or |