equal
deleted
inserted
replaced
33 \item Given the regular expressions $r_1 = \ONE$ and $r_2 = |
33 \item Given the regular expressions $r_1 = \ONE$ and $r_2 = |
34 \ZERO$ and $r_3 = a$. How many strings can the regular |
34 \ZERO$ and $r_3 = a$. How many strings can the regular |
35 expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
35 expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
36 |
36 |
37 \item Give regular expressions for (a) decimal numbers and for |
37 \item Give regular expressions for (a) decimal numbers and for |
38 (b) binary numbers. (Hint: Observe that the empty string |
38 (b) binary numbers. Hint: Observe that the empty string |
39 is not a number. Also observe that leading 0s are |
39 is not a number. Also observe that leading 0s are |
40 normally not written.) |
40 normally not written---for example the JSON format for numbers |
|
41 explicitly forbids this. |
41 |
42 |
42 \item Decide whether the following two regular expressions are |
43 \item Decide whether the following two regular expressions are |
43 equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot |
44 equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot |
44 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
45 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
45 |
46 |