equal
deleted
inserted
replaced
125 string or only the empty string), \textit{somechars} (for |
125 string or only the empty string), \textit{somechars} (for |
126 regular expressions that match some non-empty string), |
126 regular expressions that match some non-empty string), |
127 \textit{infinitestrings} (for regular expressions that can match |
127 \textit{infinitestrings} (for regular expressions that can match |
128 infinitely many strings). |
128 infinitely many strings). |
129 |
129 |
130 \item There are two kinds of automata that are generate for |
130 \item There are two kinds of automata that are generated for |
131 regular expression matching---DFAs and NFAs. (1) Regular expression engines like |
131 regular expression matching---DFAs and NFAs. (1) Regular expression engines like |
132 the one in Python generate NFAs. Explain what is the problem with such |
132 the one in Python generate NFAs. Explain what is the problem with such |
133 NFAs and what is the reason why they use NFAs. (2) Regular expression |
133 NFAs and what is the reason why they use NFAs. (2) Regular expression |
134 engines like the one in Rust generate DFAs. Explain what is the |
134 engines like the one in Rust generate DFAs. Explain what is the |
135 problem with these regex engines and also what is the problem with $a^{\{1000\}}$ |
135 problem with these regex engines and also what is the problem with $a^{\{1000\}}$ |