hws/hw01.tex
changeset 444 3056a4c071b0
parent 438 84608b4b3578
child 498 ea47c3b8f35f
equal deleted inserted replaced
443:cd43d8c6eb84 444:3056a4c071b0
    52 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings
    52 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings
    53       are in $A^4$? (2) Consider also the case of $A^4$ where one of
    53       are in $A^4$? (2) Consider also the case of $A^4$ where one of
    54       the strings in $A$ is the empty string, for example $A =
    54       the strings in $A$ is the empty string, for example $A =
    55       \{[a], [b], [c], []\}$.
    55       \{[a], [b], [c], []\}$.
    56 
    56 
    57 \item How many basic regular expressions are there to match
    57 \item (1)How many basic regular expressions are there to match
    58       the string $abcd$? (ii) How many if they cannot include
    58       the string $abcd$? (2) How many if they cannot include
    59       $\ONE$ and $\ZERO$? (iii) How many if they are also not
    59       $\ONE$ and $\ZERO$? (3) How many if they are also not
    60       allowed to contain stars? (iv) How many if they are also
    60       allowed to contain stars? (4) How many if they are also
    61       not allowed to contain $\_ + \_$?
    61       not allowed to contain $\_ + \_$?
    62 
    62 
    63 \item When are two regular expressions equivalent? Can you
    63 \item When are two regular expressions equivalent? Can you
    64       think of instances where two regular expressions match
    64       think of instances where two regular expressions match
    65       the same strings, but it is not so obvious that they do?
    65       the same strings, but it is not so obvious that they do?
    66       For example $a + b$ and $b + a$ do not count\ldots they
    66       For example $a + b$ and $b + a$ do not count\ldots they
    67       obviously match the same strings, namely $[a]$ and
    67       obviously match the same strings, namely $[a]$ and
    68       $[b]$.
    68       $[b]$.
    69 
    69 
    70 \item What is meant by the notions \emph{evil regular expressions}
    70 \item What is meant by the notions \emph{evil regular expressions}
    71       and \emph{catastrophic backtracking}? 
    71       and by \emph{catastrophic backtracking}? 
    72 
    72 
    73 \item \POSTSCRIPT  
    73 \item \POSTSCRIPT  
    74 \end{enumerate}
    74 \end{enumerate}
    75 
    75 
    76 \end{document}
    76 \end{document}