10 |
10 |
11 |
11 |
12 \section*{Homework 5} |
12 \section*{Homework 5} |
13 |
13 |
14 \begin{enumerate} |
14 \begin{enumerate} |
|
15 \item Consider the basic regular expressions |
|
16 |
|
17 \begin{center} |
|
18 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
|
19 \end{center} |
|
20 |
|
21 and suppose you want to show a property $P(r)$ for all regular |
|
22 expressions $r$ by structural induction. Write down which cases do you |
|
23 need to analyse. State clearly the induction hypotheses if applicable |
|
24 in a case. |
|
25 |
|
26 \item Define a regular expression, written $ALL$, that can match |
|
27 every string. This definition should be in terms of the |
|
28 following extended regular expressions: |
|
29 |
|
30 \begin{center} |
|
31 $r ::= \varnothing \;|\; |
|
32 \epsilon \;|\; |
|
33 c \;|\; |
|
34 r_1 + r_2 \;|\; |
|
35 r_1 \cdot r_2 \;|\; |
|
36 r^* \;|\; |
|
37 \sim r$ |
|
38 \end{center} |
|
39 |
|
40 \item Assume the delimiters for comments are \texttt{$\slash$*} |
|
41 and \texttt{*$\slash$}. Give a regular expression that can |
|
42 recognise comments of the form |
|
43 |
|
44 \begin{center} |
|
45 \texttt{$\slash$*~\ldots{}~*$\slash$} |
|
46 \end{center} |
|
47 |
|
48 where the three dots stand for arbitrary characters, but not |
|
49 comment delimiters. |
|
50 |
15 \item Define the following regular expressions |
51 \item Define the following regular expressions |
16 |
52 |
17 \begin{center} |
53 \begin{center} |
18 \begin{tabular}{ll} |
54 \begin{tabular}{ll} |
19 $r^+$ & (one or more matches)\\ |
55 $r^+$ & (one or more matches)\\ |
22 $r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\ |
58 $r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\ |
23 & \phantom{(}assumption $m \le n$)\\ |
59 & \phantom{(}assumption $m \le n$)\\ |
24 \end{tabular} |
60 \end{tabular} |
25 \end{center} |
61 \end{center} |
26 |
62 |
27 in terms of the usual regular expressions |
63 in terms of the usual basic regular expressions |
28 |
64 |
29 \begin{center} |
65 \begin{center} |
30 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
66 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
31 \end{center} |
67 \end{center} |
32 |
68 |
|
69 \item Give the regular expressions for lexing a language |
|
70 consisting of identifiers, left-parenthesis \texttt{(}, |
|
71 right-parenthesis \texttt{)}, numbers that can be either |
|
72 positive or negative, and the operations \texttt{+}, |
|
73 \texttt{-} and \texttt{*}. |
33 |
74 |
|
75 Decide whether the following strings |
|
76 can be lexed in this language? |
34 |
77 |
35 \item Recall the definitions for $Der$ and $der$ from the lectures. |
78 \begin{enumerate} |
|
79 \item \texttt{"(a3+3)*b"} |
|
80 \item \texttt{")()++-33"} |
|
81 \item \texttt{"(b42/3)*3"} |
|
82 \end{enumerate} |
|
83 |
|
84 In case they can, give the corresponding token sequences. (Hint: |
|
85 Observe the maximal munch rule and the priorities of your regular |
|
86 expressions that make the process of lexing unambiguous.) |
|
87 |
|
88 \item (Optional) Recall the definitions for $Der$ and $der$ from the lectures. |
36 Prove by induction on $r$ the property that |
89 Prove by induction on $r$ the property that |
37 |
90 |
38 \[ |
91 \[ |
39 L(der\,c\,r) = Der\,c\,(L(r)) |
92 L(der\,c\,r) = Der\,c\,(L(r)) |
40 \] |
93 \] |
41 |
94 |
42 holds. |
95 holds. |
|
96 |
43 \end{enumerate} |
97 \end{enumerate} |
44 |
98 |
45 \end{document} |
99 \end{document} |
46 |
100 |
47 %%% Local Variables: |
101 %%% Local Variables: |