1 \documentclass{article} |
|
2 \usepackage{charter} |
|
3 \usepackage{hyperref} |
|
4 \usepackage{amssymb} |
|
5 \usepackage{amsmath} |
|
6 \usepackage{tikz} |
|
7 \usetikzlibrary{automata} |
|
8 |
|
9 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
10 |
|
11 \begin{document} |
|
12 |
|
13 \section*{Homework 5} |
|
14 |
|
15 \begin{enumerate} |
|
16 \item Define the following regular expressions |
|
17 |
|
18 \begin{center} |
|
19 \begin{tabular}{ll} |
|
20 $r^+$ & (one or more matches)\\ |
|
21 $r^?$ & (zero or one match)\\ |
|
22 $r^{\{n\}}$ & (exactly $n$ matches)\\ |
|
23 $r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\ |
|
24 & \phantom{(}assumption $m \le n$)\\ |
|
25 \end{tabular} |
|
26 \end{center} |
|
27 |
|
28 in terms of the usual regular expressions |
|
29 |
|
30 \begin{center} |
|
31 $r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
|
32 \end{center} |
|
33 |
|
34 \item Given a deterministic finite automata $A(Q, q_0, F, \delta)$, |
|
35 define which language is recognised by this automaton. |
|
36 |
|
37 \item Given the following deterministic finite automata over the alphabet |
|
38 $\{a, b\}$, find an automaton that recognises the complement language. |
|
39 (Hint: Recall that for the algorithm from the lectures, the automaton needs to be |
|
40 in completed form, that is have a transition for every letter from the alphabet.) |
|
41 |
|
42 \begin{center} |
|
43 \begin{tikzpicture}[scale=3, line width=0.7mm] |
|
44 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
45 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
|
46 \path[->] (q0) edge node[above] {$a$} (q1) |
|
47 (q1) edge [loop right] node {$b$} () |
|
48 ; |
|
49 \end{tikzpicture} |
|
50 \end{center} |
|
51 |
|
52 \item Given the following deterministic finite automaton |
|
53 |
|
54 \begin{center} |
|
55 \begin{tikzpicture}[scale=3, line width=0.7mm] |
|
56 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
57 \node[state,accepting] (q1) at ( 1,1) {$q_1$}; |
|
58 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
|
59 \path[->] (q0) edge node[above] {$b$} (q1) |
|
60 (q1) edge [loop above] node[above] {$a$} () |
|
61 (q2) edge [loop above] node[above] {$a, b$} () |
|
62 (q1) edge node[above] {$b$} (q2) |
|
63 (q0) edge[bend right] node[below] {$a$} (q2) |
|
64 ; |
|
65 \end{tikzpicture} |
|
66 \end{center} |
|
67 find the corresponding minimal automaton. State clearly which nodes |
|
68 can be merged. |
|
69 |
|
70 \item Given the following non-deterministic finite automaton over the alphabet $\{a, b\}$, |
|
71 find a deterministic finite automaton that recognises the same language: |
|
72 |
|
73 \begin{center} |
|
74 \begin{tikzpicture}[scale=3, line width=0.7mm] |
|
75 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
76 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
77 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
|
78 \path[->] (q0) edge node[above] {$a$} (q1) |
|
79 (q0) edge [loop above] node[above] {$b$} () |
|
80 (q0) edge [loop below] node[below] {$a$} () |
|
81 (q1) edge node[above] {$a$} (q2) |
|
82 ; |
|
83 \end{tikzpicture} |
|
84 \end{center} |
|
85 |
|
86 \item |
|
87 Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
|
88 |
|
89 \begin{center} |
|
90 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
91 \node[state, initial, accepting] (q0) at ( 0,1) {$q_0$}; |
|
92 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
|
93 \node[state] (q2) at ( 2,1) {$q_2$}; |
|
94 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
95 (q1) edge[bend left] node[above] {$b$} (q0) |
|
96 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
97 (q1) edge node[above] {$a$} (q2) |
|
98 (q2) edge [loop right] node {$a$} () |
|
99 (q0) edge [loop below] node {$b$} () |
|
100 ; |
|
101 \end{tikzpicture} |
|
102 \end{center} |
|
103 |
|
104 Give a regular expression that can recognise the same language as |
|
105 this automaton. (Hint: If you use Brzozwski's method, you can assume |
|
106 Arden's lemma which states that an equation of the form $q = q\cdot r + s$ |
|
107 has the unique solution $q = s \cdot r^*$.)\ |
|
108 \end{enumerate} |
|
109 |
|
110 |
|
111 \end{document} |
|
112 |
|
113 %%% Local Variables: |
|
114 %%% mode: latex |
|
115 %%% TeX-master: t |
|
116 %%% End: |
|