2 \usepackage{charter} |
2 \usepackage{charter} |
3 \usepackage{hyperref} |
3 \usepackage{hyperref} |
4 \usepackage{amssymb} |
4 \usepackage{amssymb} |
5 \usepackage{amsmath} |
5 \usepackage{amsmath} |
6 |
6 |
|
7 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
8 |
7 \begin{document} |
9 \begin{document} |
8 |
10 |
9 \section*{Homework 4} |
11 \section*{Homework 4} |
10 |
12 |
11 \begin{enumerate} |
13 \begin{enumerate} |
12 \item Assume you have an alphabet consisting of the letters $a$, $b$ and $c$ only. |
14 \item Give an automaton that can recognise the language |
13 (a) Find a regular expression that recognises the two strings $ab$ and $ac$. (b) |
15 $L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$. |
14 Find a regular expression that matches all strings \emph{except} these two strings. |
16 |
15 Note, you can only use regular expressions of the form |
17 \item Assume that $s^{-1}$ stands for the operation of reversing a |
|
18 string $s$. Given the following \emph{reversing} function on regular |
|
19 expressions |
|
20 |
|
21 and the set |
|
22 |
16 \begin{center} |
23 \begin{center} |
17 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
24 $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ |
18 \end{center} |
25 \end{center} |
19 |
26 |
20 \item Define the function $zeroable$ which takes a regular expression as argument |
27 prove that |
21 and returns a boolean.\footnote{In an earlier version there was an error.} The |
28 |
22 function should satisfy the following property: |
|
23 \begin{center} |
29 \begin{center} |
24 $zeroable(r)$ \;if and only if\; $L(r) = \varnothing$ |
30 $L(rev(r)) = Rev (L(r))$ |
25 \end{center} |
31 \end{center} |
26 |
32 |
27 \item Define the tokens and regular expressions for a language |
33 holds. |
28 consisting of numbers, left-parenthesis (, right-parenthesis ), |
|
29 identifiers and the operations $+$, $-$ and $*$. Can the following strings |
|
30 in this language be lexed? |
|
31 |
34 |
32 \begin{itemize} |
35 \item Palindromes |
33 \item \texttt{"}$(a + 3) * b$\texttt{"} |
|
34 \item \texttt{"}$)()++ -33$\texttt{"} |
|
35 \item \texttt{"}$(a / 3) * 3$\texttt{"} |
|
36 \end{itemize} |
|
37 |
36 |
38 \item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
37 \item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
39 argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
38 argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
40 that it filters out all comments and whitespace from the result. |
39 that it filters out all comments and whitespace from the result. |
41 |
40 |