diff -r d01568431081 -r 858f62bc930a handouts/ho03.tex --- a/handouts/ho03.tex Sat Oct 22 13:11:33 2016 +0100 +++ b/handouts/ho03.tex Sat Oct 22 15:18:11 2016 +0100 @@ -17,7 +17,7 @@ widely known rather recently. Still let us in this lecture have a closer look at automata and their relation to regular expressions. This will help us with understanding why the -regular expression matchers in Python and Ruby are so slow +regular expression matchers in Python, Ruby and Java are so slow with certain regular expressions. The central definition is:\medskip @@ -177,7 +177,8 @@ have to ``consume'' any part of the input string, but ``silently'' change to a different state. In the left picture, for example, if you are in the starting state, you can -silently move either to $q_1$ or $q_2$. +silently move either to $q_1$ or $q_2$. This silent +transition is also often called \emph{$\epsilon$-transition}. \subsubsection*{Thompson Construction} @@ -558,7 +559,7 @@ constructed. First have a look at the second equation: the left-hand side is $q_1$ and the right-hand side $q_0\,a$. The right-hand side is essentially all possible ways how to end up -in $q_1$. There is only one incoming edge from $q_0$ consuming +in node $q_1$. There is only one incoming edge from $q_0$ consuming an $a$. Therefore the right hand side is this state followed by character---in this case $q_0\,a$. Now lets have a look at the third equation: there are two incoming