9 \section*{Homework 3} |
9 \section*{Homework 3} |
10 |
10 |
11 \begin{enumerate} |
11 \begin{enumerate} |
12 \item What is a regular language? |
12 \item What is a regular language? |
13 |
13 |
14 \item Assume you have an alphabet consisting of the letters $a$, $b$ and $c$ only. |
14 \item Assume you have an alphabet consisting of the letters |
15 (1) Find a regular expression that recognises the two strings $ab$ and $ac$. (2) |
15 $a$, $b$ and $c$ only. (1) Find a regular expression |
16 Find a regular expression that matches all strings \emph{except} these two strings. |
16 that recognises the two strings $ab$ and $ac$. (2) Find |
17 Note, you can only use regular expressions of the form |
17 a regular expression that matches all strings |
|
18 \emph{except} these two strings. Note, you can only use |
|
19 regular expressions of the form |
|
20 |
|
21 \begin{center} $r ::= |
|
22 \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; |
|
23 r_1 \cdot r_2 \;|\; r^*$ |
|
24 \end{center} |
|
25 |
|
26 \item Define the function \textit{zeroable} which takes a |
|
27 regular expression as argument and returns a boolean. |
|
28 The function should satisfy the following property: |
|
29 |
18 \begin{center} |
30 \begin{center} |
19 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
31 $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$ |
20 \end{center} |
|
21 |
|
22 \item Define the function $zeroable$ which takes a regular expression as argument |
|
23 and returns a boolean. The |
|
24 function should satisfy the following property: |
|
25 \begin{center} |
|
26 $zeroable(r)$ \;if and only if\; $L(r) = \varnothing$ |
|
27 \end{center} |
32 \end{center} |
28 |
33 |
29 \item Define the tokens and regular expressions for a language |
34 \item Define the tokens and regular expressions for a language |
30 consisting of numbers, left-parenthesis (, right-parenthesis ), |
35 consisting of numbers, left-parenthesis $($, |
31 identifiers and the operations $+$, $-$ and $*$. Can the following strings |
36 right-parenthesis $)$, identifiers and the operations $+$, |
32 in this language be lexed? |
37 $-$ and $*$. Can the following strings in this language |
|
38 be lexed? |
33 |
39 |
34 \begin{itemize} |
40 \begin{itemize} |
35 \item \texttt{"}$(a + 3) * b$\texttt{"} |
41 \item $(a + 3) * b$ |
36 \item \texttt{"}$)()++ -33$\texttt{"} |
42 \item $)()++ -33$ |
37 \item \texttt{"}$(a / 3) * 3$\texttt{"} |
43 \item $(a / 3) * 3$ |
38 \end{itemize} |
44 \end{itemize} |
39 |
45 |
|
46 In case they can, can you give the corresponding token |
|
47 sequences. |
40 |
48 |
41 In case they can, can you give the corresponding token sequences. |
|
42 \end{enumerate} |
49 \end{enumerate} |
43 |
50 |
44 |
51 |
45 |
52 |
46 \end{document} |
53 \end{document} |