11 \section*{Homework 4} |
11 \section*{Homework 4} |
12 |
12 |
13 \begin{enumerate} |
13 \begin{enumerate} |
14 \item Why is every finite set of strings a regular language? |
14 \item Why is every finite set of strings a regular language? |
15 |
15 |
|
16 \item What is the language recognised by the regular expressions $(\varnothing^*)^*$. |
16 |
17 |
17 \item Give an automaton that can recognise the language |
18 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$ |
18 $L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$. |
19 is it possible for $L(r)$ to be empty? |
19 |
20 |
20 \item Assume that $s^{-1}$ stands for the operation of reversing a |
21 \item Assume that $s^{-1}$ stands for the operation of reversing a |
21 string $s$. Given the following \emph{reversing} function on regular |
22 string $s$. Given the following \emph{reversing} function on regular |
22 expressions |
23 expressions |
23 |
24 |
45 $L(rev(r)) = Rev (L(r))$ |
46 $L(rev(r)) = Rev (L(r))$ |
46 \end{center} |
47 \end{center} |
47 |
48 |
48 holds. |
49 holds. |
49 |
50 |
50 \item Palindromes |
51 \item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings |
|
52 that do not contain any substring $bb$ and end in $a$. |
|
53 |
|
54 \item Assume the delimiters for comments are \texttt{$\slash$*} and \texttt{*$\slash$}. |
|
55 Give a regular expression that can recognise comments |
|
56 of the form |
|
57 |
|
58 \begin{center} |
|
59 \texttt{$\slash$*~\ldots{}~*$\slash$} |
|
60 \end{center} |
|
61 |
|
62 where the three dots stand for arbitrary characters, but not comment delimiters. |
|
63 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
|
64 that can recognise any character.) |
|
65 |
|
66 \item Geven the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$. |
|
67 The starting state is $q_0$ and the final state is $q_1$. The transition |
|
68 function is given by |
|
69 |
|
70 \begin{center} |
|
71 \begin{tabular}{l} |
|
72 $(q_0, a) \rightarrow q_0$\\ |
|
73 $(q_0, b) \rightarrow q_1$\\ |
|
74 $(q_1, b) \rightarrow q_1$ |
|
75 \end{tabular} |
|
76 \end{center} |
|
77 |
|
78 What is the languages recognised by this automaton? |
|
79 |
|
80 \item Give a deterministic finite automaton that can recognise |
|
81 the language $L(a^*\cdot b\cdot b^*)$. |
|
82 |
51 |
83 |
52 \item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
84 \item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
53 argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
85 argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
54 that it filters out all comments and whitespace from the result. |
86 that it filters out all comments and whitespace from the result. |
55 |
87 |
57 implements the \texttt{findAll} function. This function takes a regular |
89 implements the \texttt{findAll} function. This function takes a regular |
58 expressions and a string, and returns all substrings in this string that |
90 expressions and a string, and returns all substrings in this string that |
59 match the regular expression. |
91 match the regular expression. |
60 \end{enumerate} |
92 \end{enumerate} |
61 |
93 |
62 |
94 % explain what is a context-free grammar and the language it generates |
|
95 % |
|
96 % What does it mean for two regular expressions to be equivalent. |
|
97 % |
|
98 % Define the language L(M) accepted by a deterministic finite automaton M. |
|
99 % |
|
100 % Draw a parse tree for.... |
|
101 % |
|
102 % does (a + b)*b+ and (a*b+) + (b*b+) define the same language |
|
103 % |
|
104 % What does it mean for a grammar to be ambiguous |
63 |
105 |
64 \end{document} |
106 \end{document} |
65 |
107 |
66 %%% Local Variables: |
108 %%% Local Variables: |
67 %%% mode: latex |
109 %%% mode: latex |