hws/hw03.tex
changeset 647 180600c04da2
parent 577 7a437f1f689d
child 652 4642e2073808
--- 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