equal
deleted
inserted
replaced
4 \usepackage{../langs} |
4 \usepackage{../langs} |
5 \usepackage{../graphics} |
5 \usepackage{../graphics} |
6 |
6 |
7 |
7 |
8 \begin{document} |
8 \begin{document} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2020} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2020, 2022} |
10 |
10 |
11 \section*{Handout 3 (Finite Automata)} |
11 \section*{Handout 3 (Finite Automata)} |
12 |
12 |
13 |
13 |
14 Every formal language and compiler course I know of bombards you first |
14 Every formal language and compiler course I know of bombards you first |
1065 the number of subsets you can form for sets of $n$ states). This blow |
1065 the number of subsets you can form for sets of $n$ states). This blow |
1066 up in the number of states in the DFA is again bad news for how |
1066 up in the number of states in the DFA is again bad news for how |
1067 quickly you can decide whether a string is accepted by a DFA or |
1067 quickly you can decide whether a string is accepted by a DFA or |
1068 not. So the caveat with DFAs is that they might make the task of |
1068 not. So the caveat with DFAs is that they might make the task of |
1069 finding the next state trivial, but might require $2^n$ times as many |
1069 finding the next state trivial, but might require $2^n$ times as many |
1070 states then a NFA.\bigskip |
1070 states than a NFA.\bigskip |
1071 |
1071 |
1072 \noindent |
1072 \noindent |
1073 To conclude this section, how conveniently we can |
1073 To conclude this section, how conveniently we can |
1074 implement the subset construction with our versions of NFAs and |
1074 implement the subset construction with our versions of NFAs and |
1075 DFAs? Very conveniently. The code is just: |
1075 DFAs? Very conveniently. The code is just: |
1570 \noindent |
1570 \noindent |
1571 Where have the derivatives gone? Did we just forget them? Well, they |
1571 Where have the derivatives gone? Did we just forget them? Well, they |
1572 actually do play a role of generating a DFA from a regular expression. |
1572 actually do play a role of generating a DFA from a regular expression. |
1573 And we can also see this in our implementation\ldots{}because there is |
1573 And we can also see this in our implementation\ldots{}because there is |
1574 one flaw in our representation of automata and transitions as partial |
1574 one flaw in our representation of automata and transitions as partial |
1575 functions. We can represent automata with infinite states, which is |
1575 functions....remember I said something about fishy things. |
|
1576 Namely, we can represent automata with infinite states, which is |
1576 actually forbidden by the definition of what an automaton is. We can |
1577 actually forbidden by the definition of what an automaton is. We can |
1577 exploit this flaw as follows: Suppose our alphabet consists of the |
1578 exploit this flaw as follows: Suppose our alphabet consists of the |
1578 characters $c_1$ to $c_n$. Then we can generate an ``automaton'' |
1579 characters $c_1$ to $c_n$. Then we can generate an ``automaton'' |
1579 (it is not really one because it has infinite states) by taking |
1580 (it is not really one because it has infinite states) by taking |
1580 as starting state the regular expression $r$ for which we |
1581 as starting state the regular expression $r$ for which we |
1611 |
1612 |
1612 \noindent |
1613 \noindent |
1613 I let you implement this ``automaton''. |
1614 I let you implement this ``automaton''. |
1614 |
1615 |
1615 While this makes all sense (modulo the flaw with the infinite states), |
1616 While this makes all sense (modulo the flaw with the infinite states), |
1616 does this automaton teach us anything? The answer is no, because it |
1617 does this automaton teach us anything new? The answer is no, because it |
1617 boils down to just another implementation of the Brzozowski |
1618 boils down to just another implementation of the Brzozowski |
1618 algorithm. There \emph{is} something interesting in this construction |
1619 algorithm from Lecture 2. There \emph{is} however something interesting |
|
1620 in this construction |
1619 which Brzozowski already cleverly found out, because there is |
1621 which Brzozowski already cleverly found out, because there is |
1620 a way to restrict the number of states to something finite. |
1622 a way to restrict the number of states to something finite. |
|
1623 Meaning it would give us a real automaton. |
1621 However, this would lead us far, far away from what we should |
1624 However, this would lead us far, far away from what we should |
1622 discuss here. |
1625 discuss here. |
1623 |
1626 |
1624 |
1627 |
1625 |
1628 |