# HG changeset patch # User Christian Urban # Date 1633778955 -3600 # Node ID 97b622202547b24bfec05fcaa2c91816d97c414a # Parent b53ac1bb5f436a7e8dedfe39543e4a8f6256e116 updated diff -r b53ac1bb5f43 -r 97b622202547 hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r b53ac1bb5f43 -r 97b622202547 hws/hw04.tex --- a/hws/hw04.tex Wed Oct 06 20:43:35 2021 +0100 +++ b/hws/hw04.tex Sat Oct 09 12:29:15 2021 +0100 @@ -119,13 +119,22 @@ \item What is the purpose of the record regular expression in the Sulzmann \& Lu algorithm? -\item Recall the functions \textit{nullable} and \textit{zeroable}. - Define recursive functions \textit{atmostempty} (for regular expressions - that match no string or only the empty string), \textit{somechars} (for regular - expressions that match some non-empty string), \textit{infinitestrings} (for regular - expressions that can match infinitely many strings). +\item Recall the functions \textit{nullable} and + \textit{zeroable}. Define recursive functions + \textit{atmostempty} (for regular expressions that match no + string or only the empty string), \textit{somechars} (for + regular expressions that match some non-empty string), + \textit{infinitestrings} (for regular expressions that can match + infinitely many strings). - +\item There are two kinds of automata that are generate for + regular expression matching---DFAs and NFAs. (1) Regular expression engines like + the one in Python generate NFAs. Explain what is the problem with such + NFAs and what is the reason why they use NFAs. (2) Regular expression + engines like the one in Rust generate DFAs. Explain what is the + problem with these regex engines and also what is the problem with $a^{\{1000\}}$ + in these engines. + %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so %that it filters out all comments and whitespace from the result.