35 $\textit{zeroable(r)} \;\text{if and only if}\; |
35 $\textit{zeroable(r)} \;\text{if and only if}\; |
36 L(r) = \{\}$ |
36 L(r) = \{\}$ |
37 \end{center} |
37 \end{center} |
38 |
38 |
39 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two |
39 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two |
40 states, say $q_0$ and $q_1$. The starting state is $q_0$ and the |
40 states, say $Q_0$ and $Q_1$. The starting state is $Q_0$ and the |
41 final state is $q_1$. The transition function is given by |
41 final state is $Q_1$. The transition function is given by |
42 |
42 |
43 \begin{center} |
43 \begin{center} |
44 \begin{tabular}{l} |
44 \begin{tabular}{l} |
45 $(q_0, a) \rightarrow q_0$\\ |
45 $(Q_0, a) \rightarrow Q_0$\\ |
46 $(q_0, b) \rightarrow q_1$\\ |
46 $(Q_0, b) \rightarrow Q_1$\\ |
47 $(q_1, b) \rightarrow q_1$ |
47 $(Q_1, b) \rightarrow Q_1$ |
48 \end{tabular} |
48 \end{tabular} |
49 \end{center} |
49 \end{center} |
50 |
50 |
51 What is the language recognised by this automaton? |
51 What is the language recognised by this automaton? |
52 |
52 |
53 \item Give a non-deterministic finite automaton that can |
53 \item Give a non-deterministic finite automaton that can |
54 recognise the language $L(a\cdot (a + b)^* \cdot c)$. |
54 recognise the language $L(a\cdot (a + b)^* \cdot c)$. |
55 |
55 |
56 \item Given a deterministic finite automaton $A(Q, q_0, F, |
56 \item Given a deterministic finite automaton $A(\varSigma, Q, Q_0, F, |
57 \delta)$, define which language is recognised by this |
57 \delta)$, define which language is recognised by this |
58 automaton. Can you define also the language defined by a |
58 automaton. Can you define also the language defined by a |
59 non-deterministic automaton? |
59 non-deterministic automaton? |
60 |
60 |
61 \item Given the following deterministic finite automaton over |
61 \item Given the following deterministic finite automaton over |
68 \begin{center} |
68 \begin{center} |
69 \begin{tikzpicture}[>=stealth',very thick,auto, |
69 \begin{tikzpicture}[>=stealth',very thick,auto, |
70 every state/.style={minimum size=0pt, |
70 every state/.style={minimum size=0pt, |
71 inner sep=2pt,draw=blue!50,very thick, |
71 inner sep=2pt,draw=blue!50,very thick, |
72 fill=blue!20},scale=2] |
72 fill=blue!20},scale=2] |
73 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
73 \node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
74 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
74 \node[state, accepting] (q1) at ( 1,1) {$Q_1$}; |
75 \path[->] (q0) edge node[above] {$a$} (q1) |
75 \path[->] (q0) edge node[above] {$a$} (q1) |
76 (q1) edge [loop right] node {$b$} (); |
76 (q1) edge [loop right] node {$b$} (); |
77 \end{tikzpicture} |
77 \end{tikzpicture} |
78 \end{center} |
78 \end{center} |
79 |
79 |
104 \begin{center} |
104 \begin{center} |
105 \begin{tikzpicture}[>=stealth',very thick,auto, |
105 \begin{tikzpicture}[>=stealth',very thick,auto, |
106 every state/.style={minimum size=0pt, |
106 every state/.style={minimum size=0pt, |
107 inner sep=2pt,draw=blue!50,very thick, |
107 inner sep=2pt,draw=blue!50,very thick, |
108 fill=blue!20},scale=2] |
108 fill=blue!20},scale=2] |
109 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
109 \node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
110 \node[state] (q1) at ( 1,1) {$q_1$}; |
110 \node[state] (q1) at ( 1,1) {$Q_1$}; |
111 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
111 \node[state, accepting] (q2) at ( 2,1) {$Q_2$}; |
112 \path[->] (q0) edge node[above] {$a$} (q1) |
112 \path[->] (q0) edge node[above] {$a$} (q1) |
113 (q0) edge [loop above] node[above] {$b$} () |
113 (q0) edge [loop above] node[above] {$b$} () |
114 (q0) edge [loop below] node[below] {$a$} () |
114 (q0) edge [loop below] node[below] {$a$} () |
115 (q1) edge node[above] {$a$} (q2); |
115 (q1) edge node[above] {$a$} (q2); |
116 \end{tikzpicture} |
116 \end{tikzpicture} |
117 \end{center} |
117 \end{center} |
118 |
118 |
119 \item Given the following deterministic finite automaton over the |
119 \item \textbf{(Deleted for 2017)} |
|
120 Given the following deterministic finite automaton over the |
120 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
121 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
121 case states can be merged, state clearly which states can be merged. |
122 case states can be merged, state clearly which states can be merged. |
122 |
123 |
123 \begin{center} |
124 \begin{center} |
124 \begin{tikzpicture}[>=stealth',very thick,auto, |
125 \begin{tikzpicture}[>=stealth',very thick,auto, |
125 every state/.style={minimum size=0pt, |
126 every state/.style={minimum size=0pt, |
126 inner sep=2pt,draw=blue!50,very thick, |
127 inner sep=2pt,draw=blue!50,very thick, |
127 fill=blue!20},scale=2] |
128 fill=blue!20},scale=2] |
128 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
129 \node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
129 \node[state] (q1) at ( 1,1) {$q_1$}; |
130 \node[state] (q1) at ( 1,1) {$Q_1$}; |
130 \node[state, accepting] (q4) at ( 2,1) {$q_4$}; |
131 \node[state, accepting] (q4) at ( 2,1) {$Q_4$}; |
131 \node[state] (q2) at (0.5,0) {$q_2$}; |
132 \node[state] (q2) at (0.5,0) {$Q_2$}; |
132 \node[state] (q3) at (1.5,0) {$q_3$}; |
133 \node[state] (q3) at (1.5,0) {$Q_3$}; |
133 \path[->] (q0) edge node[above] {$0$} (q1) |
134 \path[->] (q0) edge node[above] {$0$} (q1) |
134 (q0) edge node[right] {$1$} (q2) |
135 (q0) edge node[right] {$1$} (q2) |
135 (q1) edge node[above] {$0$} (q4) |
136 (q1) edge node[above] {$0$} (q4) |
136 (q1) edge node[right] {$1$} (q2) |
137 (q1) edge node[right] {$1$} (q2) |
137 (q2) edge node[above] {$0$} (q3) |
138 (q2) edge node[above] {$0$} (q3) |
147 \begin{center} |
148 \begin{center} |
148 \begin{tikzpicture}[scale=2,>=stealth',very thick,auto, |
149 \begin{tikzpicture}[scale=2,>=stealth',very thick,auto, |
149 every state/.style={minimum size=0pt, |
150 every state/.style={minimum size=0pt, |
150 inner sep=2pt,draw=blue!50,very thick, |
151 inner sep=2pt,draw=blue!50,very thick, |
151 fill=blue!20}] |
152 fill=blue!20}] |
152 \node[state, initial, accepting] (q0) at ( 0,1) {$q_0$}; |
153 \node[state, initial, accepting] (q0) at ( 0,1) {$Q_0$}; |
153 \node[state, accepting] (q1) at ( 1,1) {$q_1$}; |
154 \node[state, accepting] (q1) at ( 1,1) {$Q_1$}; |
154 \node[state] (q2) at ( 2,1) {$q_2$}; |
155 \node[state] (q2) at ( 2,1) {$Q_2$}; |
155 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
156 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
156 (q1) edge[bend left] node[above] {$b$} (q0) |
157 (q1) edge[bend left] node[above] {$b$} (q0) |
157 (q2) edge[bend left=50] node[below] {$b$} (q0) |
158 (q2) edge[bend left=50] node[below] {$b$} (q0) |
158 (q1) edge node[above] {$a$} (q2) |
159 (q1) edge node[above] {$a$} (q2) |
159 (q2) edge [loop right] node {$a$} () |
160 (q2) edge [loop right] node {$a$} () |