equal
deleted
inserted
replaced
7 \begin{document} |
7 \begin{document} |
8 |
8 |
9 \section*{Homework 2} |
9 \section*{Homework 2} |
10 |
10 |
11 \begin{enumerate} |
11 \begin{enumerate} |
|
12 \item What is the meaning of a regular expression? Give an inductive definition. |
|
13 |
|
14 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 = \varnothing$ and $r_3 = a$. |
|
15 How many strings can the regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
|
16 |
|
17 |
12 \item Give regular expressions for (a) decimal numbers and for (b) binary numbers. |
18 \item Give regular expressions for (a) decimal numbers and for (b) binary numbers. |
13 (Hint: Observe that the empty string is not a number. Also observe that leading 0s |
19 (Hint: Observe that the empty string is not a number. Also observe that leading 0s |
14 are normally not written.) |
20 are normally not written.) |
15 |
21 |
16 \item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and |
22 \item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and |