2 \usepackage{../style} |
2 \usepackage{../style} |
3 |
3 |
4 \usepackage{tikz} |
4 \usepackage{tikz} |
5 \usetikzlibrary{automata} |
5 \usetikzlibrary{automata} |
6 |
6 |
7 |
|
8 %%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
9 |
|
10 \begin{document} |
7 \begin{document} |
11 |
8 |
12 \section*{Homework 4} |
9 \section*{Homework 4} |
13 |
10 |
14 \begin{enumerate} |
11 \begin{enumerate} |
15 \item Why is every finite set of strings a regular language? |
|
16 |
|
17 \item What is the language recognised by the regular expressions $(\varnothing^*)^*$. |
|
18 |
12 |
19 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$, |
13 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$, |
20 is it possible for $L(r)$ to be empty? |
14 is it possible for $L(r)$ to be empty? |
21 |
15 |
22 \item Define the tokens and regular expressions for a language |
16 \item Define the tokens and regular expressions for a language |
23 consisting of numbers, left-parenthesis $($, |
17 consisting of numbers, left-parenthesis $($, right-parenthesis $)$, |
24 right-parenthesis $)$, identifiers and the operations $+$, |
18 identifiers and the operations $+$, $-$ and $*$. Can the following |
25 $-$ and $*$. Can the following strings in this language |
19 strings in this language be lexed? |
26 be lexed? |
|
27 |
20 |
28 \begin{itemize} |
21 \begin{itemize} |
29 \item $(a + 3) * b$ |
22 \item $(a + 3) * b$ |
30 \item $)()++ -33$ |
23 \item $)()++ -33$ |
31 \item $(a / 3) * 3$ |
24 \item $(a / 3) * 3$ |
32 \end{itemize} |
25 \end{itemize} |
33 |
26 |
34 In case they can, can you give the corresponding token |
27 In case they can, can you give the corresponding token |
35 sequences. |
28 sequences. |
36 |
29 |
37 \item Assume that $s^{-1}$ stands for the operation of reversing a |
30 \item Assume that $s^{-1}$ stands for the operation of reversing a |
38 string $s$. Given the following \emph{reversing} function on regular |
31 string $s$. Given the following \emph{reversing} function on regular |
39 expressions |
32 expressions |
40 |
33 |
41 \begin{center} |
34 \begin{center} |
42 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
35 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
43 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
36 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
44 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
37 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
45 $rev(c)$ & $\dn$ & $c$\\ |
38 $rev(c)$ & $\dn$ & $c$\\ |
46 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
39 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
47 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
40 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
48 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
41 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
49 \end{tabular} |
42 \end{tabular} |
50 \end{center} |
43 \end{center} |
51 |
44 |
|
45 and the set |
52 |
46 |
53 and the set |
47 \begin{center} |
|
48 $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ |
|
49 \end{center} |
54 |
50 |
55 \begin{center} |
51 prove whether |
56 $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ |
|
57 \end{center} |
|
58 |
52 |
59 prove whether |
53 \begin{center} |
|
54 $L(rev(r)) = Rev (L(r))$ |
|
55 \end{center} |
60 |
56 |
61 \begin{center} |
57 holds. |
62 $L(rev(r)) = Rev (L(r))$ |
|
63 \end{center} |
|
64 |
58 |
65 holds. |
59 \item Assume the delimiters for comments are \texttt{$\slash$*} and |
|
60 \texttt{*$\slash$}. Give a regular expression that can recognise |
|
61 comments of the form |
66 |
62 |
67 \item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings |
63 \begin{center} |
68 that do not contain any substring $bb$ and end in $a$. |
64 \texttt{$\slash$*~\ldots{}~*$\slash$} |
|
65 \end{center} |
69 |
66 |
70 \item Assume the delimiters for comments are \texttt{$\slash$*} and \texttt{*$\slash$}. |
67 where the three dots stand for arbitrary characters, but not comment delimiters. |
71 Give a regular expression that can recognise comments |
68 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
72 of the form |
69 that can recognise any character, and a regular expression \texttt{NOT} that recognises |
73 |
70 the complement of a regular expression.) |
74 \begin{center} |
|
75 \texttt{$\slash$*~\ldots{}~*$\slash$} |
|
76 \end{center} |
|
77 |
|
78 where the three dots stand for arbitrary characters, but not comment delimiters. |
|
79 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
|
80 that can recognise any character, and a regular expression \texttt{NOT} that recognises |
|
81 the complement of a regular expression.) |
|
82 |
71 |
83 |
72 |
84 |
73 |
85 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
74 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
86 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
75 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |