diff -r 2abd285c66d1 -r 180600c04da2 hws/hw03.tex --- a/hws/hw03.tex Thu Oct 03 11:12:00 2019 +0100 +++ b/hws/hw03.tex Fri Oct 04 11:21:30 2019 +0100 @@ -9,6 +9,10 @@ \HEADER \begin{enumerate} +\item The regular expression matchers in Java, Python and Ruby can be + very slow with some (basic) regular expressions. What is the main + reason for this inefficient computation? + \item What is a regular language? Are there alternative ways to define this notion? If yes, give an explanation why they define the same notion. @@ -27,14 +31,14 @@ r_1 \cdot r_2 \;|\; r^*$ \end{center} -\item Define the function \textit{zeroable} which takes a - regular expression as argument and returns a boolean. - The function should satisfy the following property: - - \begin{center} - $\textit{zeroable(r)} \;\text{if and only if}\; - L(r) = \{\}$ - \end{center} +%\item Define the function \textit{zeroable} which takes a +% regular expression as argument and returns a boolean. +% The function should satisfy the following property: +% +% \begin{center} +% $\textit{zeroable(r)} \;\text{if and only if}\; +% L(r) = \{\}$ +% \end{center} \item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $Q_0$ and $Q_1$. The starting state is $Q_0$ and the