18 |
16 |
19 \item What is the language recognised by the regular expressions $(\varnothing^*)^*$. |
17 \item What is the language recognised by the regular expressions $(\varnothing^*)^*$. |
20 |
18 |
21 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$, |
19 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$, |
22 is it possible for $L(r)$ to be empty? |
20 is it possible for $L(r)$ to be empty? |
|
21 |
|
22 \item Define the tokens and regular expressions for a language |
|
23 consisting of numbers, left-parenthesis $($, |
|
24 right-parenthesis $)$, identifiers and the operations $+$, |
|
25 $-$ and $*$. Can the following strings in this language |
|
26 be lexed? |
|
27 |
|
28 \begin{itemize} |
|
29 \item $(a + 3) * b$ |
|
30 \item $)()++ -33$ |
|
31 \item $(a / 3) * 3$ |
|
32 \end{itemize} |
|
33 |
|
34 In case they can, can you give the corresponding token |
|
35 sequences. |
23 |
36 |
24 \item Assume that $s^{-1}$ stands for the operation of reversing a |
37 \item Assume that $s^{-1}$ stands for the operation of reversing a |
25 string $s$. Given the following \emph{reversing} function on regular |
38 string $s$. Given the following \emph{reversing} function on regular |
26 expressions |
39 expressions |
27 |
40 |
65 where the three dots stand for arbitrary characters, but not comment delimiters. |
78 where the three dots stand for arbitrary characters, but not comment delimiters. |
66 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
79 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
67 that can recognise any character, and a regular expression \texttt{NOT} that recognises |
80 that can recognise any character, and a regular expression \texttt{NOT} that recognises |
68 the complement of a regular expression.) |
81 the complement of a regular expression.) |
69 |
82 |
70 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$. |
|
71 The starting state is $q_0$ and the final state is $q_1$. The transition |
|
72 function is given by |
|
73 |
|
74 \begin{center} |
|
75 \begin{tabular}{l} |
|
76 $(q_0, a) \rightarrow q_0$\\ |
|
77 $(q_0, b) \rightarrow q_1$\\ |
|
78 $(q_1, b) \rightarrow q_1$ |
|
79 \end{tabular} |
|
80 \end{center} |
|
81 |
|
82 What is the languages recognised by this automaton? |
|
83 |
|
84 \item Give a non-deterministic finite automaton that can recognise |
|
85 the language $L(a\cdot (a + b)^* \cdot c)$. |
|
86 |
|
87 |
|
88 \item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$, |
|
89 find the corresponding minimal automaton. In case states can be merged, |
|
90 state clearly which states can |
|
91 be merged. |
|
92 |
|
93 \begin{center} |
|
94 \begin{tikzpicture}[scale=3, line width=0.7mm] |
|
95 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
96 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
97 \node[state, accepting] (q4) at ( 2,1) {$q_4$}; |
|
98 \node[state] (q2) at (0.5,0) {$q_2$}; |
|
99 \node[state] (q3) at (1.5,0) {$q_3$}; |
|
100 \path[->] (q0) edge node[above] {$0$} (q1) |
|
101 (q0) edge node[right] {$1$} (q2) |
|
102 (q1) edge node[above] {$0$} (q4) |
|
103 (q1) edge node[right] {$1$} (q2) |
|
104 (q2) edge node[above] {$0$} (q3) |
|
105 (q2) edge [loop below] node {$1$} () |
|
106 (q3) edge node[left] {$0$} (q4) |
|
107 (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0) |
|
108 (q4) edge [loop right] node {$0, 1$} () |
|
109 ; |
|
110 \end{tikzpicture} |
|
111 \end{center} |
|
112 |
83 |
113 |
84 |
114 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
85 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
115 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
86 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
116 %that it filters out all comments and whitespace from the result. |
87 %that it filters out all comments and whitespace from the result. |