equal
deleted
inserted
replaced
9 \begin{document} |
9 \begin{document} |
10 |
10 |
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? |
|
15 |
|
16 |
14 \item Give an automaton that can recognise the language |
17 \item Give an automaton that can recognise the language |
15 $L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$. |
18 $L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$. |
16 |
19 |
17 \item Assume that $s^{-1}$ stands for the operation of reversing a |
20 \item Assume that $s^{-1}$ stands for the operation of reversing a |
18 string $s$. Given the following \emph{reversing} function on regular |
21 string $s$. Given the following \emph{reversing} function on regular |
19 expressions |
22 expressions |
20 |
23 |
|
24 \begin{center} |
|
25 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
26 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
|
27 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
|
28 $rev(c)$ & $\dn$ & $c$\\ |
|
29 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
|
30 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
|
31 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
|
32 \end{tabular} |
|
33 \end{center} |
|
34 |
|
35 |
21 and the set |
36 and the set |
22 |
37 |
23 \begin{center} |
38 \begin{center} |
24 $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ |
39 $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ |
25 \end{center} |
40 \end{center} |
26 |
41 |
27 prove that |
42 prove whether |
28 |
43 |
29 \begin{center} |
44 \begin{center} |
30 $L(rev(r)) = Rev (L(r))$ |
45 $L(rev(r)) = Rev (L(r))$ |
31 \end{center} |
46 \end{center} |
32 |
47 |