16 |
16 |
17 \begin{enumerate} |
17 \begin{enumerate} |
18 \item Consider the basic regular expressions |
18 \item Consider the basic regular expressions |
19 |
19 |
20 \begin{center} |
20 \begin{center} |
21 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
21 $r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
22 \end{center} |
22 \end{center} |
23 |
23 |
24 and suppose you want to show a property $P(r)$ for all regular |
24 and suppose you want to show a property $P(r)$ for all |
25 expressions $r$ by structural induction. Write down which cases do you |
25 regular expressions $r$ by structural induction. Write |
26 need to analyse. State clearly the induction hypotheses if applicable |
26 down which cases do you need to analyse. State clearly |
27 in a case. |
27 the induction hypotheses if applicable in a case. |
28 |
28 |
29 \item Define a regular expression, written $ALL$, that can match |
29 \item Define a regular expression, written $ALL$, that can |
30 every string. This definition should be in terms of the |
30 match every string. This definition should be in terms |
31 following extended regular expressions: |
31 of the following extended regular expressions: |
32 |
32 |
33 \begin{center} |
33 \begin{center} |
34 $r ::= \varnothing \;|\; |
34 $r ::= \ZERO \;|\; |
35 \epsilon \;|\; |
35 \ONE \;|\; |
36 c \;|\; |
36 c \;|\; |
37 r_1 + r_2 \;|\; |
37 r_1 + r_2 \;|\; |
38 r_1 \cdot r_2 \;|\; |
38 r_1 \cdot r_2 \;|\; |
39 r^* \;|\; |
39 r^* \;|\; |
40 \sim r$ |
40 \sim r$ |
64 \end{center} |
64 \end{center} |
65 |
65 |
66 in terms of the usual basic regular expressions |
66 in terms of the usual basic regular expressions |
67 |
67 |
68 \begin{center} |
68 \begin{center} |
69 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
69 $r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
70 \end{center} |
70 \end{center} |
71 |
71 |
72 \item Give the regular expressions for lexing a language |
72 \item Give the regular expressions for lexing a language |
73 consisting of identifiers, left-parenthesis \texttt{(}, |
73 consisting of identifiers, left-parenthesis \texttt{(}, |
74 right-parenthesis \texttt{)}, numbers that can be either |
74 right-parenthesis \texttt{)}, numbers that can be either |
75 positive or negative, and the operations \texttt{+}, |
75 positive or negative, and the operations \texttt{+}, |
76 \texttt{-} and \texttt{*}. |
76 \texttt{-} and \texttt{*}. |
77 |
77 |
78 Decide whether the following strings |
78 Decide whether the following strings can be lexed in |
79 can be lexed in this language? |
79 this language? |
80 |
80 |
81 \begin{enumerate} |
81 \begin{enumerate} |
82 \item \texttt{"(a3+3)*b"} |
82 \item \texttt{"(a3+3)*b"} |
83 \item \texttt{")()++-33"} |
83 \item \texttt{")()++-33"} |
84 \item \texttt{"(b42/3)*3"} |
84 \item \texttt{"(b42/3)*3"} |
86 |
86 |
87 In case they can, give the corresponding token sequences. (Hint: |
87 In case they can, give the corresponding token sequences. (Hint: |
88 Observe the maximal munch rule and the priorities of your regular |
88 Observe the maximal munch rule and the priorities of your regular |
89 expressions that make the process of lexing unambiguous.) |
89 expressions that make the process of lexing unambiguous.) |
90 |
90 |
91 \item (Optional) Recall the definitions for $Der$ and $der$ from the lectures. |
91 \item (Optional) Recall the definitions for $Der$ and $der$ |
92 Prove by induction on $r$ the property that |
92 from the lectures. Prove by induction on $r$ the |
|
93 property that |
93 |
94 |
94 \[ |
95 \[ |
95 L(der\,c\,r) = Der\,c\,(L(r)) |
96 L(der\,c\,r) = Der\,c\,(L(r)) |
96 \] |
97 \] |
97 |
98 |
98 holds. |
99 holds. |
99 |
100 |
100 \end{enumerate} |
101 \end{enumerate} |
101 |
102 |
102 \end{document} |
103 \end{document} |
103 |
104 |