11 %$\epsilon$. |
11 %$\epsilon$. |
12 |
12 |
13 \begin{document} |
13 \begin{document} |
14 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017} |
14 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017} |
15 |
15 |
16 \section*{Handout 3 (Automata)} |
16 \section*{Handout 3 (Finite Automata)} |
17 |
17 |
18 Every formal language and compiler course I know of bombards you first |
18 Every formal language and compiler course I know of bombards you first |
19 with automata and then to a much, much smaller extend with regular |
19 with automata and then to a much, much smaller extend with regular |
20 expressions. As you can see, this course is turned upside down: |
20 expressions. As you can see, this course is turned upside down: |
21 regular expressions come first. The reason is that regular expressions |
21 regular expressions come first. The reason is that regular expressions |
22 are easier to reason about and the notion of derivatives, although |
22 are easier to reason about and the notion of derivatives, although |
23 already quite old, only became more widely known rather |
23 already quite old, only became more widely known rather |
24 recently. Still let us in this lecture have a closer look at automata |
24 recently. Still let us in this lecture have a closer look at automata |
25 and their relation to regular expressions. This will help us with |
25 and their relation to regular expressions. This will help us with |
26 understanding why the regular expression matchers in Python, Ruby and |
26 understanding why the regular expression matchers in Python, Ruby and |
27 Java are so slow with certain regular expressions. The central |
27 Java are so slow with certain regular expressions. |
28 definition is:\medskip |
28 |
|
29 |
|
30 \subsection*{Deterministic Finite Automata} |
|
31 |
|
32 Their definition is as follows:\medskip |
29 |
33 |
30 \noindent |
34 \noindent |
31 A \emph{deterministic finite automaton} (DFA), say $A$, is |
35 A \emph{deterministic finite automaton} (DFA), say $A$, is |
32 given by a four-tuple written $A(Q, q_0, F, \delta)$ where |
36 given by a four-tuple written $A(Qs, Q_0, F, \delta)$ where |
33 |
37 |
34 \begin{itemize} |
38 \begin{itemize} |
35 \item $Q$ is a finite set of states, |
39 \item $Qs$ is a finite set of states, |
36 \item $q_0 \in Q$ is the start state, |
40 \item $Q_0 \in Qs$ is the start state, |
37 \item $F \subseteq Q$ are the accepting states, and |
41 \item $F \subseteq Qs$ are the accepting states, and |
38 \item $\delta$ is the transition function. |
42 \item $\delta$ is the transition function. |
39 \end{itemize} |
43 \end{itemize} |
40 |
44 |
41 \noindent The transition function determines how to |
45 \noindent The transition function determines how to ``transition'' |
42 ``transition'' from one state to the next state with respect |
46 from one state to the next state with respect to a character. We have |
43 to a character. We have the assumption that these transition |
47 the assumption that these transition functions do not need to be |
44 functions do not need to be defined everywhere: so it can be |
48 defined everywhere: so it can be the case that given a character there |
45 the case that given a character there is no next state, in |
49 is no next state, in which case we need to raise a kind of ``failure |
46 which case we need to raise a kind of ``failure exception''. A |
50 exception''. That means actually we have partial functions as |
47 typical example of a DFA is |
51 transitions---see our implementation later on. A typical example of a |
|
52 DFA is |
48 |
53 |
49 \begin{center} |
54 \begin{center} |
50 \begin{tikzpicture}[>=stealth',very thick,auto, |
55 \begin{tikzpicture}[>=stealth',very thick,auto, |
51 every state/.style={minimum size=0pt, |
56 every state/.style={minimum size=0pt, |
52 inner sep=2pt,draw=blue!50,very thick, |
57 inner sep=2pt,draw=blue!50,very thick, |
53 fill=blue!20},scale=2] |
58 fill=blue!20},scale=2] |
54 \node[state,initial] (q_0) {$q_0$}; |
59 \node[state,initial] (Q_0) {$Q_0$}; |
55 \node[state] (q_1) [right=of q_0] {$q_1$}; |
60 \node[state] (Q_1) [right=of Q_0] {$Q_1$}; |
56 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
61 \node[state] (Q_2) [below right=of Q_0] {$Q_2$}; |
57 \node[state] (q_3) [right=of q_2] {$q_3$}; |
62 \node[state] (Q_3) [right=of Q_2] {$Q_3$}; |
58 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
63 \node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$}; |
59 \path[->] (q_0) edge node [above] {$a$} (q_1); |
64 \path[->] (Q_0) edge node [above] {$a$} (Q_1); |
60 \path[->] (q_1) edge node [above] {$a$} (q_4); |
65 \path[->] (Q_1) edge node [above] {$a$} (Q_4); |
61 \path[->] (q_4) edge [loop right] node {$a, b$} (); |
66 \path[->] (Q_4) edge [loop right] node {$a, b$} (); |
62 \path[->] (q_3) edge node [right] {$a$} (q_4); |
67 \path[->] (Q_3) edge node [right] {$a$} (Q_4); |
63 \path[->] (q_2) edge node [above] {$a$} (q_3); |
68 \path[->] (Q_2) edge node [above] {$a$} (Q_3); |
64 \path[->] (q_1) edge node [right] {$b$} (q_2); |
69 \path[->] (Q_1) edge node [right] {$b$} (Q_2); |
65 \path[->] (q_0) edge node [above] {$b$} (q_2); |
70 \path[->] (Q_0) edge node [above] {$b$} (Q_2); |
66 \path[->] (q_2) edge [loop left] node {$b$} (); |
71 \path[->] (Q_2) edge [loop left] node {$b$} (); |
67 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {$b$} (q_0); |
72 \path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {$b$} (Q_0); |
68 \end{tikzpicture} |
73 \end{tikzpicture} |
69 \end{center} |
74 \end{center} |
70 |
75 |
71 \noindent In this graphical notation, the accepting state |
76 \noindent In this graphical notation, the accepting state $Q_4$ is |
72 $q_4$ is indicated with double circles. Note that there can be |
77 indicated with double circles. Note that there can be more than one |
73 more than one accepting state. It is also possible that a DFA |
78 accepting state. It is also possible that a DFA has no accepting |
74 has no accepting states at all, or that the starting state is |
79 states at all, or that the starting state is also an accepting |
75 also an accepting state. In the case above the transition |
80 state. In the case above the transition function is defined everywhere |
76 function is defined everywhere and can be given as a table as |
81 and can also be given as a table as follows: |
77 follows: |
|
78 |
82 |
79 \[ |
83 \[ |
80 \begin{array}{lcl} |
84 \begin{array}{lcl} |
81 (q_0, a) &\rightarrow& q_1\\ |
85 (Q_0, a) &\rightarrow& Q_1\\ |
82 (q_0, b) &\rightarrow& q_2\\ |
86 (Q_0, b) &\rightarrow& Q_2\\ |
83 (q_1, a) &\rightarrow& q_4\\ |
87 (Q_1, a) &\rightarrow& Q_4\\ |
84 (q_1, b) &\rightarrow& q_2\\ |
88 (Q_1, b) &\rightarrow& Q_2\\ |
85 (q_2, a) &\rightarrow& q_3\\ |
89 (Q_2, a) &\rightarrow& Q_3\\ |
86 (q_2, b) &\rightarrow& q_2\\ |
90 (Q_2, b) &\rightarrow& Q_2\\ |
87 (q_3, a) &\rightarrow& q_4\\ |
91 (Q_3, a) &\rightarrow& Q_4\\ |
88 (q_3, b) &\rightarrow& q_0\\ |
92 (Q_3, b) &\rightarrow& Q_0\\ |
89 (q_4, a) &\rightarrow& q_4\\ |
93 (Q_4, a) &\rightarrow& Q_4\\ |
90 (q_4, b) &\rightarrow& q_4\\ |
94 (Q_4, b) &\rightarrow& Q_4\\ |
91 \end{array} |
95 \end{array} |
92 \] |
96 \] |
93 |
97 |
94 We need to define the notion of what language is accepted by |
98 We need to define the notion of what language is accepted by |
95 an automaton. For this we lift the transition function |
99 an automaton. For this we lift the transition function |
108 the second character and so on. Once the string is exhausted and we |
112 the second character and so on. Once the string is exhausted and we |
109 end up in an accepting state, then this string is accepted by the |
113 end up in an accepting state, then this string is accepted by the |
110 automaton. Otherwise it is not accepted. This also means that if along |
114 automaton. Otherwise it is not accepted. This also means that if along |
111 the way we hit the case where the transition function $\delta$ is not |
115 the way we hit the case where the transition function $\delta$ is not |
112 defined, we need to raise an error. In our implementation we will deal |
116 defined, we need to raise an error. In our implementation we will deal |
113 with this case elegantly by using Scala's \texttt{Try}. So $s$ is in |
117 with this case elegantly by using Scala's \texttt{Try}. So a string |
114 the \emph{language accepted by the automaton} $A(Q, q_0, F, \delta)$ |
118 $s$ is in the \emph{language accepted by the automaton} $A(Q, Q_0, F, |
115 iff |
119 \delta)$ iff |
116 |
120 |
117 \[ |
121 \[ |
118 \hat{\delta}(q_0, s) \in F |
122 \hat{\delta}(Q_0, s) \in F |
119 \] |
123 \] |
120 |
124 |
121 \noindent I let you think about a definition that describes |
125 \noindent I let you think about a definition that describes |
122 the set of strings accepted by an automaton. |
126 the set of strings accepted by an automaton. |
123 |
127 |
124 \begin{figure}[p] |
128 \begin{figure}[p] |
125 \small |
129 \small |
126 \lstinputlisting[numbers=left,linebackgroundcolor= |
130 \lstinputlisting[numbers=left,linebackgroundcolor= |
127 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
131 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
128 {../progs/dfa.scala} |
132 {../progs/dfa.scala} |
129 \caption{Scala implementation of DFAs using partial functions. |
133 \caption{A Scala implementation of DFAs using partial functions. |
130 Notice some subtleties: \texttt{deltas} implements the delta-hat |
134 Notice some subtleties: \texttt{deltas} implements the delta-hat |
131 construction by lifting the transition (partial) function to |
135 construction by lifting the transition (partial) function to |
132 lists of \texttt{C}haracters. Since \texttt{delta} is given |
136 lists of \texttt{C}haracters. Since \texttt{delta} is given |
133 as partial function, it can obviously go ``wrong'' in which |
137 as partial function, it can obviously go ``wrong'' in which |
134 case the \texttt{Try} in \texttt{accepts} catches the error and |
138 case the \texttt{Try} in \texttt{accepts} catches the error and |
135 returns \texttt{false}, that is the string is not accepted. |
139 returns \texttt{false}---that means the string is not accepted. |
136 The example implements the DFA example shown above.\label{dfa}} |
140 The example \texttt{delta} implements the DFA example shown |
|
141 earlier in the handout.\label{dfa}} |
137 \end{figure} |
142 \end{figure} |
138 |
143 |
139 A simple Scala implementation of DFAs is given in Figure~\ref{dfa}. As |
144 A simple Scala implementation for DFAs is given in |
140 you can see, there many features of the mathematical definition that |
145 Figure~\ref{dfa}. As you can see, there many features of the |
141 are quite closely reflected in the code. In the DFA-class, there is a |
146 mathematical definition that are quite closely reflected in the |
142 starting state, called \texttt{start}, with the polymorphic type |
147 code. In the DFA-class, there is a starting state, called |
143 \texttt{A}. There is a partial function \texttt{delta} for specifying |
148 \texttt{start}, with the polymorphic type \texttt{A}. (The reason for |
144 the transitions. I used partial functions for transitions in Scala; |
149 having a polymorphic types for the states and the input of DFAs will |
145 alternatives would have been \texttt{Maps} or even \texttt{Lists}. One |
150 become clearer later.) There is a partial function \texttt{delta} for |
146 of the main advantages of using partial functions is that transitions |
151 specifying the transitions. I used partial functions for representing |
147 can be quite nicely defined by a series of \texttt{case} statements |
152 the transitions in Scala; alternatives would have been \texttt{Maps} |
148 (see Lines 28 -- 38). If you need to represent an automaton |
153 or even \texttt{Lists}. One of the main advantages of using partial |
149 with a sink state (catch-all-state), you can write something like |
154 functions is that transitions can be quite nicely defined by a series |
|
155 of \texttt{case} statements (see Lines 28 -- 38). If you need to |
|
156 represent an automaton with a sink state (catch-all-state), you can |
|
157 write something like |
150 |
158 |
151 {\small\begin{lstlisting}[language=Scala,linebackgroundcolor= |
159 {\small\begin{lstlisting}[language=Scala,linebackgroundcolor= |
152 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
160 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
153 abstract class State |
161 abstract class State |
154 ... |
162 ... |
159 case (S1, 'a') => S2 |
167 case (S1, 'a') => S2 |
160 case _ => Sink |
168 case _ => Sink |
161 } |
169 } |
162 \end{lstlisting}} |
170 \end{lstlisting}} |
163 |
171 |
164 \noindent The DFA-class has also an argument for final states. It is a |
172 \noindent The DFA-class has also an argument for specifying final |
165 function from states to booleans (returns true whenever a state is |
173 states. In the implementation it is a function from states to booleans |
166 meant to be finbal; false otherwise). While this is a boolean |
174 (returns true whenever a state is meant to be final; false |
167 function, Scala allows me to use sets of states for such functions |
175 otherwise). While this boolean function is different from the sets of |
168 (see Line 40 where I initialise the DFA). |
176 states used in the mathematical definition, Scala allows me to use |
|
177 sets for such functions (see Line 40 where I initialise the DFA). |
169 |
178 |
170 I let you ponder whether this is a good implementation of DFAs. In |
179 I let you ponder whether this is a good implementation of DFAs. In |
171 doing so I hope you notice that the $Q$ component (the set of finite |
180 doing so I hope you notice that the $Qs$ component (the set of finite |
172 states) is missing from the class definition. This means that the |
181 states) is missing from the class definition. This means that the |
173 implementation allows you to do some fishy things you are not meant to |
182 implementation allows you to do some fishy things you are not meant to |
174 do with DFAs. Which fishy things could that be? |
183 do with DFAs. Which fishy things could that be? |
175 |
184 |
176 While with DFAs it will always be clear that given a character what |
185 |
177 the next state is (potentially none), it will be useful to relax this |
186 |
178 restriction. That means we have several potential successor states. We |
187 \subsection*{Non-Deterministic Finite Automata} |
179 even allow more than one starting state. The resulting construction is |
188 |
180 called a \emph{non-deterministic finite automaton} (NFA) given also as |
189 While with DFAs it will always be clear that given a state and a |
181 a four-tuple $A(Q, Q_{0s}, F, \rho)$ where |
190 character what the next state is (potentially none), it will be useful |
|
191 to relax this restriction. That means we allow to have several |
|
192 potential successor states. We even allow more than one starting |
|
193 state. The resulting construction is called a \emph{non-deterministic |
|
194 finite automaton} (NFA) given also as a four-tuple $A(Qs, Q_{0s}, F, |
|
195 \rho)$ where |
182 |
196 |
183 \begin{itemize} |
197 \begin{itemize} |
184 \item $Q$ is a finite set of states |
198 \item $Qs$ is a finite set of states |
185 \item $Q_{0s}$ are the start states ($Q_{0s} \subseteq Q$) |
199 \item $Q_{0s}$ is a set of start states ($Q_{0s} \subseteq Qs$) |
186 \item $F$ are some accepting states with $F \subseteq Q$, and |
200 \item $F$ are some accepting states with $F \subseteq Qs$, and |
187 \item $\rho$ is a transition relation. |
201 \item $\rho$ is a transition relation. |
188 \end{itemize} |
202 \end{itemize} |
189 |
203 |
190 \noindent |
204 \noindent |
191 Two typical examples of NFAs are |
205 A typical example of an NFA is |
192 \begin{center} |
206 |
193 \begin{tabular}[t]{c@{\hspace{9mm}}c} |
207 % A NFA for (ab* + b)*a |
194 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
208 \begin{center} |
195 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
209 \begin{tikzpicture}[scale=0.8,>=stealth',very thick, |
196 \node[state,initial] (q_0) {$q_0$}; |
210 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
197 \node[state] (q_1) [above=of q_0] {$q_1$}; |
211 \node[state,initial] (Q_0) {$Q_0$}; |
198 \node[state, accepting] (q_2) [below=of q_0] {$q_2$}; |
212 \node[state] (Q_1) [right=of Q_0] {$Q_1$}; |
199 \path[->] (q_0) edge node [left] {$\epsilon$} (q_1); |
213 \node[state, accepting] (Q_2) [right=of Q_1] {$Q_2$}; |
200 \path[->] (q_0) edge node [left] {$\epsilon$} (q_2); |
214 \path[->] (Q_0) edge [loop above] node {$b$} (); |
201 \path[->] (q_0) edge [loop right] node {$a$} (); |
215 \path[<-] (Q_0) edge node [below] {$b$} (Q_1); |
202 \path[->] (q_1) edge [loop above] node {$a$} (); |
216 \path[->] (Q_0) edge [bend left] node [above] {$a$} (Q_1); |
203 \path[->] (q_2) edge [loop below] node {$b$} (); |
217 \path[->] (Q_0) edge [bend right] node [below] {$a$} (Q_2); |
204 \end{tikzpicture} & |
218 \path[->] (Q_1) edge [loop above] node {$a,b$} (); |
205 |
219 \path[->] (Q_1) edge node [above] {$a$} (Q_2); |
206 \raisebox{20mm}{ |
220 \end{tikzpicture} |
207 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
221 \end{center} |
208 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
222 |
209 \node[state,initial] (r_1) {$r_1$}; |
223 \noindent |
210 \node[state] (r_2) [above=of r_1] {$r_2$}; |
224 This NFA happens to have only one starting state, but in general there |
211 \node[state, accepting] (r_3) [right=of r_1] {$r_3$}; |
225 could be more. Notice that in state $Q_0$ we might go to state $Q_1$ |
212 \path[->] (r_1) edge node [below] {$b$} (r_3); |
226 \emph{or} to state $Q_2$ when receiving an $a$. Similarly in state $Q_1$ |
213 \path[->] (r_2) edge [bend left] node [above] {$a$} (r_3); |
227 and receiving an $a$, we can stay in state $Q_1$ or go to $Q_2$. This |
214 \path[->] (r_1) edge [bend left] node [left] {$\epsilon$} (r_2); |
228 kind of choice is not allowed with DFAs. When it comes to deciding |
215 \path[->] (r_2) edge [bend left] node [right] {$a$} (r_1); |
229 whether a string is accepted by an NFA we potentially need to explore |
216 \end{tikzpicture}} |
230 all possibilities. I let you think which kind of strings this NFA |
217 \end{tabular} |
231 accepts. |
218 \end{center} |
232 |
219 |
233 |
220 \noindent There are, however, a number of points you should |
234 There are however a number of additional points you should note. Every |
221 note. Every DFA is a NFA, but not vice versa. The $\rho$ in |
235 DFA is a NFA, but not vice versa. The $\rho$ in NFAs is a transition |
222 NFAs is a transition \emph{relation} (DFAs have a transition |
236 \emph{relation} (DFAs have a transition function). The difference |
223 function). The difference between a function and a relation is |
237 between a function and a relation is that a function has always a |
224 that a function has always a single output, while a relation |
238 single output, while a relation gives, roughly speaking, several |
225 gives, roughly speaking, several outputs. Look at the NFA on |
239 outputs. Look again at the NFA above: if you are currently in the |
226 the right-hand side above: if you are currently in the state |
240 state $Q_1$ and you read a character $b$, then you can transition to |
227 $r_2$ and you read a character $a$, then you can transition to |
241 either $Q_0$ \emph{or} $Q_2$. Which route, or output, you take is not |
228 either $r_1$ \emph{or} $r_3$. Which route you take is not |
242 determined. This non-determinism can be represented by a relation. |
229 determined. This means if we need to decide whether a string |
243 |
230 is accepted by a NFA, we might have to explore all |
244 My implementation of NFAs is shown in Figure~\ref{nfa}. Perhaps |
231 possibilities. Also there is the special silent transition in |
245 interestingly, I do not use relations for my implementation of NFAs in |
232 NFAs. As mentioned already this transition means you do not |
246 Scala, and I also do not use transition functions which return a set |
233 have to ``consume'' any part of the input string, but |
247 of states (another popular choice for implementing NFAs). For reasons |
234 ``silently'' change to a different state. In the left picture, |
248 that become clear in a moment, I use sets of partial functions---see |
235 for example, if you are in the starting state, you can |
249 Line 7 in Figure~\ref{nfa}. \texttt{Starts} is now a set of states; |
236 silently move either to $q_1$ or $q_2$. This silent |
250 \texttt{fins} is again a function from states to booleans. The |
237 transition is also often called \emph{$\epsilon$-transition}. |
251 \texttt{next} function calculates the set of next states reachable |
|
252 from a state \texttt{q} by a character \texttt{c}---we go through all |
|
253 partial functions in the \texttt{delta}-set, lift it (this transformes |
|
254 the partial function into the corresponding \texttt{Option}-function |
|
255 and then apply \texttt{q} and \texttt{c}. This gives us a set of |
|
256 \texttt{Some}s and \texttt{None}s, where the \texttt{Some}s are |
|
257 filtered out by the \texttt{flatMap}. Teh function \texttt{nexts} just |
|
258 lifts this to sets of states. \texttt{Deltas} and \texttt{accept} are |
|
259 similar to the DFA definitions. |
|
260 |
|
261 \begin{figure}[t] |
|
262 \small |
|
263 \lstinputlisting[numbers=left,linebackgroundcolor= |
|
264 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
|
265 {../progs/nfa.scala} |
|
266 \caption{A Scala implementation of NFAs using sets of partial functions. |
|
267 Notice some subtleties: \texttt{deltas} implements the delta-hat |
|
268 construction by lifting the transition (partial) function to |
|
269 lists of \texttt{C}haracters. Since \texttt{delta} is given |
|
270 as partial function, it can obviously go ``wrong'' in which |
|
271 case the \texttt{Try} in \texttt{accepts} catches the error and |
|
272 returns \texttt{false}---that means the string is not accepted. |
|
273 The example \texttt{delta} implements the DFA example shown |
|
274 earlier in the handout.\label{nfa}} |
|
275 \end{figure} |
|
276 |
|
277 |
|
278 |
|
279 %This means if |
|
280 %we need to decide whether a string is accepted by a NFA, we might have |
|
281 %to explore all possibilities. Also there is the special silent |
|
282 %transition in NFAs. As mentioned already this transition means you do |
|
283 %not have to ``consume'' any part of the input string, but ``silently'' |
|
284 %change to a different state. In the left picture, for example, if you |
|
285 %are in the starting state, you can silently move either to $Q_1$ or |
|
286 %%$Q_2$. This silent transition is also often called |
|
287 %\emph{$\epsilon$-transition}. |
238 |
288 |
239 |
289 |
240 \subsubsection*{Thompson Construction} |
290 \subsubsection*{Thompson Construction} |
241 |
291 |
242 The reason for introducing NFAs is that there is a relatively |
292 The reason for introducing NFAs is that there is a relatively |
246 |
296 |
247 \begin{center} |
297 \begin{center} |
248 \begin{tabular}[t]{l@{\hspace{10mm}}l} |
298 \begin{tabular}[t]{l@{\hspace{10mm}}l} |
249 \raisebox{1mm}{$\ZERO$} & |
299 \raisebox{1mm}{$\ZERO$} & |
250 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
300 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
251 \node[state, initial] (q_0) {$\mbox{}$}; |
301 \node[state, initial] (Q_0) {$\mbox{}$}; |
252 \end{tikzpicture}\\\\ |
302 \end{tikzpicture}\\\\ |
253 \raisebox{1mm}{$\ONE$} & |
303 \raisebox{1mm}{$\ONE$} & |
254 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
304 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
255 \node[state, initial, accepting] (q_0) {$\mbox{}$}; |
305 \node[state, initial, accepting] (Q_0) {$\mbox{}$}; |
256 \end{tikzpicture}\\\\ |
306 \end{tikzpicture}\\\\ |
257 \raisebox{2mm}{$c$} & |
307 \raisebox{2mm}{$c$} & |
258 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
308 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
259 \node[state, initial] (q_0) {$\mbox{}$}; |
309 \node[state, initial] (Q_0) {$\mbox{}$}; |
260 \node[state, accepting] (q_1) [right=of q_0] {$\mbox{}$}; |
310 \node[state, accepting] (Q_1) [right=of Q_0] {$\mbox{}$}; |
261 \path[->] (q_0) edge node [below] {$c$} (q_1); |
311 \path[->] (Q_0) edge node [below] {$c$} (Q_1); |
262 \end{tikzpicture}\\\\ |
312 \end{tikzpicture}\\\\ |
263 \end{tabular} |
313 \end{tabular} |
264 \end{center} |
314 \end{center} |
265 |
315 |
266 \noindent The case for the sequence regular expression $r_1 |
316 \noindent The case for the sequence regular expression $r_1 |
268 automata representing $r_1$ and $r_2$ respectively. |
318 automata representing $r_1$ and $r_2$ respectively. |
269 |
319 |
270 \begin{center} |
320 \begin{center} |
271 \begin{tikzpicture}[node distance=3mm, |
321 \begin{tikzpicture}[node distance=3mm, |
272 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
322 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
273 \node[state, initial] (q_0) {$\mbox{}$}; |
323 \node[state, initial] (Q_0) {$\mbox{}$}; |
274 \node (r_1) [right=of q_0] {$\ldots$}; |
324 \node (r_1) [right=of Q_0] {$\ldots$}; |
275 \node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$}; |
325 \node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$}; |
276 \node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$}; |
326 \node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$}; |
277 \node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$}; |
327 \node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$}; |
278 \node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$}; |
328 \node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$}; |
279 \node (b_1) [right=of a_0] {$\ldots$}; |
329 \node (b_1) [right=of a_0] {$\ldots$}; |
280 \node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$}; |
330 \node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$}; |
281 \node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$}; |
331 \node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$}; |
282 \node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$}; |
332 \node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$}; |
283 \begin{pgfonlayer}{background} |
333 \begin{pgfonlayer}{background} |
284 \node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {}; |
334 \node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (Q_0) (r_1) (t_1) (t_2) (t_3)] {}; |
285 \node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {}; |
335 \node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {}; |
286 \node [yshift=2mm] at (1.north) {$r_1$}; |
336 \node [yshift=2mm] at (1.north) {$r_1$}; |
287 \node [yshift=2mm] at (2.north) {$r_2$}; |
337 \node [yshift=2mm] at (2.north) {$r_2$}; |
288 \end{pgfonlayer} |
338 \end{pgfonlayer} |
289 \end{tikzpicture} |
339 \end{tikzpicture} |
603 |
653 |
604 \noindent for which we can set up the following equational |
654 \noindent for which we can set up the following equational |
605 system |
655 system |
606 |
656 |
607 \begin{eqnarray} |
657 \begin{eqnarray} |
608 q_0 & = & \ONE + q_0\,b + q_1\,b + q_2\,b\\ |
658 Q_0 & = & \ONE + Q_0\,b + Q_1\,b + Q_2\,b\\ |
609 q_1 & = & q_0\,a\\ |
659 Q_1 & = & Q_0\,a\\ |
610 q_2 & = & q_1\,a + q_2\,a |
660 Q_2 & = & Q_1\,a + Q_2\,a |
611 \end{eqnarray} |
661 \end{eqnarray} |
612 |
662 |
613 \noindent There is an equation for each node in the DFA. Let |
663 \noindent There is an equation for each node in the DFA. Let |
614 us have a look how the right-hand sides of the equations are |
664 us have a look how the right-hand sides of the equations are |
615 constructed. First have a look at the second equation: the |
665 constructed. First have a look at the second equation: the |
616 left-hand side is $q_1$ and the right-hand side $q_0\,a$. The |
666 left-hand side is $Q_1$ and the right-hand side $Q_0\,a$. The |
617 right-hand side is essentially all possible ways how to end up |
667 right-hand side is essentially all possible ways how to end up |
618 in node $q_1$. There is only one incoming edge from $q_0$ consuming |
668 in node $Q_1$. There is only one incoming edge from $Q_0$ consuming |
619 an $a$. Therefore the right hand side is this |
669 an $a$. Therefore the right hand side is this |
620 state followed by character---in this case $q_0\,a$. Now lets |
670 state followed by character---in this case $Q_0\,a$. Now lets |
621 have a look at the third equation: there are two incoming |
671 have a look at the third equation: there are two incoming |
622 edges for $q_2$. Therefore we have two terms, namely $q_1\,a$ and |
672 edges for $Q_2$. Therefore we have two terms, namely $Q_1\,a$ and |
623 $q_2\,a$. These terms are separated by $+$. The first states |
673 $Q_2\,a$. These terms are separated by $+$. The first states |
624 that if in state $q_1$ consuming an $a$ will bring you to |
674 that if in state $Q_1$ consuming an $a$ will bring you to |
625 $q_2$, and the secont that being in $q_2$ and consuming an $a$ |
675 $Q_2$, and the secont that being in $Q_2$ and consuming an $a$ |
626 will make you stay in $q_2$. The right-hand side of the |
676 will make you stay in $Q_2$. The right-hand side of the |
627 first equation is constructed similarly: there are three |
677 first equation is constructed similarly: there are three |
628 incoming edges, therefore there are three terms. There is |
678 incoming edges, therefore there are three terms. There is |
629 one exception in that we also ``add'' $\ONE$ to the |
679 one exception in that we also ``add'' $\ONE$ to the |
630 first equation, because it corresponds to the starting state |
680 first equation, because it corresponds to the starting state |
631 in the DFA. |
681 in the DFA. |
632 |
682 |
633 Having constructed the equational system, the question is |
683 Having constructed the equational system, the question is |
634 how to solve it? Remarkably the rules are very similar to |
684 how to solve it? Remarkably the rules are very similar to |
635 solving usual linear equational systems. For example the |
685 solving usual linear equational systems. For example the |
636 second equation does not contain the variable $q_1$ on the |
686 second equation does not contain the variable $Q_1$ on the |
637 right-hand side of the equation. We can therefore eliminate |
687 right-hand side of the equation. We can therefore eliminate |
638 $q_1$ from the system by just substituting this equation |
688 $Q_1$ from the system by just substituting this equation |
639 into the other two. This gives |
689 into the other two. This gives |
640 |
690 |
641 \begin{eqnarray} |
691 \begin{eqnarray} |
642 q_0 & = & \ONE + q_0\,b + q_0\,a\,b + q_2\,b\\ |
692 Q_0 & = & \ONE + Q_0\,b + Q_0\,a\,b + Q_2\,b\\ |
643 q_2 & = & q_0\,a\,a + q_2\,a |
693 Q_2 & = & Q_0\,a\,a + Q_2\,a |
644 \end{eqnarray} |
694 \end{eqnarray} |
645 |
695 |
646 \noindent where in Equation (4) we have two occurences |
696 \noindent where in Equation (4) we have two occurences |
647 of $q_0$. Like the laws about $+$ and $\cdot$, we can simplify |
697 of $Q_0$. Like the laws about $+$ and $\cdot$, we can simplify |
648 Equation (4) to obtain the following two equations: |
698 Equation (4) to obtain the following two equations: |
649 |
699 |
650 \begin{eqnarray} |
700 \begin{eqnarray} |
651 q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\ |
701 Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\ |
652 q_2 & = & q_0\,a\,a + q_2\,a |
702 Q_2 & = & Q_0\,a\,a + Q_2\,a |
653 \end{eqnarray} |
703 \end{eqnarray} |
654 |
704 |
655 \noindent Unfortunately we cannot make any more progress with |
705 \noindent Unfortunately we cannot make any more progress with |
656 substituting equations, because both (6) and (7) contain the |
706 substituting equations, because both (6) and (7) contain the |
657 variable on the left-hand side also on the right-hand side. |
707 variable on the left-hand side also on the right-hand side. |
658 Here we need to now use a law that is different from the usual |
708 Here we need to now use a law that is different from the usual |
659 laws about linear equations. It is called \emph{Arden's rule}. |
709 laws about linear equations. It is called \emph{Arden's rule}. |
660 It states that if an equation is of the form $q = q\,r + s$ |
710 It states that if an equation is of the form $q = q\,r + s$ |
661 then it can be transformed to $q = s\, r^*$. Since we can |
711 then it can be transformed to $q = s\, r^*$. Since we can |
662 assume $+$ is symmetric, Equation (7) is of that form: $s$ is |
712 assume $+$ is symmetric, Equation (7) is of that form: $s$ is |
663 $q_0\,a\,a$ and $r$ is $a$. That means we can transform |
713 $Q_0\,a\,a$ and $r$ is $a$. That means we can transform |
664 (7) to obtain the two new equations |
714 (7) to obtain the two new equations |
665 |
715 |
666 \begin{eqnarray} |
716 \begin{eqnarray} |
667 q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\ |
717 Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_2\,b\\ |
668 q_2 & = & q_0\,a\,a\,(a^*) |
718 Q_2 & = & Q_0\,a\,a\,(a^*) |
669 \end{eqnarray} |
719 \end{eqnarray} |
670 |
720 |
671 \noindent Now again we can substitute the second equation into |
721 \noindent Now again we can substitute the second equation into |
672 the first in order to eliminate the variable $q_2$. |
722 the first in order to eliminate the variable $Q_2$. |
673 |
723 |
674 \begin{eqnarray} |
724 \begin{eqnarray} |
675 q_0 & = & \ONE + q_0\,(b + a\,b) + q_0\,a\,a\,(a^*)\,b |
725 Q_0 & = & \ONE + Q_0\,(b + a\,b) + Q_0\,a\,a\,(a^*)\,b |
676 \end{eqnarray} |
726 \end{eqnarray} |
677 |
727 |
678 \noindent Pulling $q_0$ out as a single factor gives: |
728 \noindent Pulling $Q_0$ out as a single factor gives: |
679 |
729 |
680 \begin{eqnarray} |
730 \begin{eqnarray} |
681 q_0 & = & \ONE + q_0\,(b + a\,b + a\,a\,(a^*)\,b) |
731 Q_0 & = & \ONE + Q_0\,(b + a\,b + a\,a\,(a^*)\,b) |
682 \end{eqnarray} |
732 \end{eqnarray} |
683 |
733 |
684 \noindent This equation is again of the form so that we can |
734 \noindent This equation is again of the form so that we can |
685 apply Arden's rule ($r$ is $b + a\,b + a\,a\,(a^*)\,b$ and $s$ |
735 apply Arden's rule ($r$ is $b + a\,b + a\,a\,(a^*)\,b$ and $s$ |
686 is $\ONE$). This gives as solution for $q_0$ the following |
736 is $\ONE$). This gives as solution for $Q_0$ the following |
687 regular expression: |
737 regular expression: |
688 |
738 |
689 \begin{eqnarray} |
739 \begin{eqnarray} |
690 q_0 & = & \ONE\,(b + a\,b + a\,a\,(a^*)\,b)^* |
740 Q_0 & = & \ONE\,(b + a\,b + a\,a\,(a^*)\,b)^* |
691 \end{eqnarray} |
741 \end{eqnarray} |
692 |
742 |
693 \noindent Since this is a regular expression, we can simplify |
743 \noindent Since this is a regular expression, we can simplify |
694 away the $\ONE$ to obtain the slightly simpler regular |
744 away the $\ONE$ to obtain the slightly simpler regular |
695 expression |
745 expression |
696 |
746 |
697 \begin{eqnarray} |
747 \begin{eqnarray} |
698 q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^* |
748 Q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^* |
699 \end{eqnarray} |
749 \end{eqnarray} |
700 |
750 |
701 \noindent |
751 \noindent |
702 Now we can unwind this process and obtain the solutions |
752 Now we can unwind this process and obtain the solutions |
703 for the other equations. This gives: |
753 for the other equations. This gives: |
704 |
754 |
705 \begin{eqnarray} |
755 \begin{eqnarray} |
706 q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\\ |
756 Q_0 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\\ |
707 q_1 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\\ |
757 Q_1 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\\ |
708 q_2 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^* |
758 Q_2 & = & (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^* |
709 \end{eqnarray} |
759 \end{eqnarray} |
710 |
760 |
711 \noindent Finally, we only need to ``add'' up the equations |
761 \noindent Finally, we only need to ``add'' up the equations |
712 which correspond to a terminal state. In our running example, |
762 which correspond to a terminal state. In our running example, |
713 this is just $q_2$. Consequently, a regular expression |
763 this is just $Q_2$. Consequently, a regular expression |
714 that recognises the same language as the automaton is |
764 that recognises the same language as the automaton is |
715 |
765 |
716 \[ |
766 \[ |
717 (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^* |
767 (b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a)^* |
718 \] |
768 \] |
755 \begin{center} |
805 \begin{center} |
756 \begin{tikzpicture}[>=stealth',very thick,auto, |
806 \begin{tikzpicture}[>=stealth',very thick,auto, |
757 every state/.style={minimum size=0pt, |
807 every state/.style={minimum size=0pt, |
758 inner sep=2pt,draw=blue!50,very thick, |
808 inner sep=2pt,draw=blue!50,very thick, |
759 fill=blue!20}] |
809 fill=blue!20}] |
760 \node[state,initial] (q_0) {$q_0$}; |
810 \node[state,initial] (Q_0) {$Q_0$}; |
761 \node[state] (q_1) [right=of q_0] {$q_1$}; |
811 \node[state] (Q_1) [right=of Q_0] {$Q_1$}; |
762 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
812 \node[state] (Q_2) [below right=of Q_0] {$Q_2$}; |
763 \node[state] (q_3) [right=of q_2] {$q_3$}; |
813 \node[state] (Q_3) [right=of Q_2] {$Q_3$}; |
764 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
814 \node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$}; |
765 \path[->] (q_0) edge node [above] {$a$} (q_1); |
815 \path[->] (Q_0) edge node [above] {$a$} (Q_1); |
766 \path[->] (q_1) edge node [above] {$a$} (q_4); |
816 \path[->] (Q_1) edge node [above] {$a$} (Q_4); |
767 \path[->] (q_4) edge [loop right] node {$a, b$} (); |
817 \path[->] (Q_4) edge [loop right] node {$a, b$} (); |
768 \path[->] (q_3) edge node [right] {$a$} (q_4); |
818 \path[->] (Q_3) edge node [right] {$a$} (Q_4); |
769 \path[->] (q_2) edge node [above] {$a$} (q_3); |
819 \path[->] (Q_2) edge node [above] {$a$} (Q_3); |
770 \path[->] (q_1) edge node [right] {$b$} (q_2); |
820 \path[->] (Q_1) edge node [right] {$b$} (Q_2); |
771 \path[->] (q_0) edge node [above] {$b$} (q_2); |
821 \path[->] (Q_0) edge node [above] {$b$} (Q_2); |
772 \path[->] (q_2) edge [loop left] node {$b$} (); |
822 \path[->] (Q_2) edge [loop left] node {$b$} (); |
773 \path[->] (q_3) edge [bend left=95, looseness=1.3] node |
823 \path[->] (Q_3) edge [bend left=95, looseness=1.3] node |
774 [below] {$b$} (q_0); |
824 [below] {$b$} (Q_0); |
775 \end{tikzpicture} |
825 \end{tikzpicture} |
776 \end{center} |
826 \end{center} |
777 |
827 |
778 \noindent In Step 1 and 2 we consider essentially a triangle |
828 \noindent In Step 1 and 2 we consider essentially a triangle |
779 of the form |
829 of the form |
790 \draw (1,0) -- (1, 4); |
840 \draw (1,0) -- (1, 4); |
791 \draw (2,0) -- (2, 3); |
841 \draw (2,0) -- (2, 3); |
792 \draw (3,0) -- (3, 2); |
842 \draw (3,0) -- (3, 2); |
793 \draw (4,0) -- (4, 1); |
843 \draw (4,0) -- (4, 1); |
794 |
844 |
795 \draw (0.5,-0.5) node {$q_0$}; |
845 \draw (0.5,-0.5) node {$Q_0$}; |
796 \draw (1.5,-0.5) node {$q_1$}; |
846 \draw (1.5,-0.5) node {$Q_1$}; |
797 \draw (2.5,-0.5) node {$q_2$}; |
847 \draw (2.5,-0.5) node {$Q_2$}; |
798 \draw (3.5,-0.5) node {$q_3$}; |
848 \draw (3.5,-0.5) node {$Q_3$}; |
799 |
849 |
800 \draw (-0.5, 3.5) node {$q_1$}; |
850 \draw (-0.5, 3.5) node {$Q_1$}; |
801 \draw (-0.5, 2.5) node {$q_2$}; |
851 \draw (-0.5, 2.5) node {$Q_2$}; |
802 \draw (-0.5, 1.5) node {$q_3$}; |
852 \draw (-0.5, 1.5) node {$Q_3$}; |
803 \draw (-0.5, 0.5) node {$q_4$}; |
853 \draw (-0.5, 0.5) node {$Q_4$}; |
804 |
854 |
805 \draw (0.5,0.5) node {\large$\star$}; |
855 \draw (0.5,0.5) node {\large$\star$}; |
806 \draw (1.5,0.5) node {\large$\star$}; |
856 \draw (1.5,0.5) node {\large$\star$}; |
807 \draw (2.5,0.5) node {\large$\star$}; |
857 \draw (2.5,0.5) node {\large$\star$}; |
808 \draw (3.5,0.5) node {\large$\star$}; |
858 \draw (3.5,0.5) node {\large$\star$}; |
809 \end{tikzpicture} |
859 \end{tikzpicture} |
810 \end{center} |
860 \end{center} |
811 |
861 |
812 \noindent where the lower row is filled with stars, because in |
862 \noindent where the lower row is filled with stars, because in |
813 the corresponding pairs there is always one state that is |
863 the corresponding pairs there is always one state that is |
814 accepting ($q_4$) and a state that is non-accepting (the other |
864 accepting ($Q_4$) and a state that is non-accepting (the other |
815 states). |
865 states). |
816 |
866 |
817 Now in Step 3 we need to fill in more stars according whether |
867 Now in Step 3 we need to fill in more stars according whether |
818 one of the next-state pairs are marked. We have to do this |
868 one of the next-state pairs are marked. We have to do this |
819 for every unmarked field until there is no change anymore. |
869 for every unmarked field until there is no change anymore. |
831 \draw (1,0) -- (1, 4); |
881 \draw (1,0) -- (1, 4); |
832 \draw (2,0) -- (2, 3); |
882 \draw (2,0) -- (2, 3); |
833 \draw (3,0) -- (3, 2); |
883 \draw (3,0) -- (3, 2); |
834 \draw (4,0) -- (4, 1); |
884 \draw (4,0) -- (4, 1); |
835 |
885 |
836 \draw (0.5,-0.5) node {$q_0$}; |
886 \draw (0.5,-0.5) node {$Q_0$}; |
837 \draw (1.5,-0.5) node {$q_1$}; |
887 \draw (1.5,-0.5) node {$Q_1$}; |
838 \draw (2.5,-0.5) node {$q_2$}; |
888 \draw (2.5,-0.5) node {$Q_2$}; |
839 \draw (3.5,-0.5) node {$q_3$}; |
889 \draw (3.5,-0.5) node {$Q_3$}; |
840 |
890 |
841 \draw (-0.5, 3.5) node {$q_1$}; |
891 \draw (-0.5, 3.5) node {$Q_1$}; |
842 \draw (-0.5, 2.5) node {$q_2$}; |
892 \draw (-0.5, 2.5) node {$Q_2$}; |
843 \draw (-0.5, 1.5) node {$q_3$}; |
893 \draw (-0.5, 1.5) node {$Q_3$}; |
844 \draw (-0.5, 0.5) node {$q_4$}; |
894 \draw (-0.5, 0.5) node {$Q_4$}; |
845 |
895 |
846 \draw (0.5,0.5) node {\large$\star$}; |
896 \draw (0.5,0.5) node {\large$\star$}; |
847 \draw (1.5,0.5) node {\large$\star$}; |
897 \draw (1.5,0.5) node {\large$\star$}; |
848 \draw (2.5,0.5) node {\large$\star$}; |
898 \draw (2.5,0.5) node {\large$\star$}; |
849 \draw (3.5,0.5) node {\large$\star$}; |
899 \draw (3.5,0.5) node {\large$\star$}; |
852 \draw (0.5,3.5) node {\large$\star$}; |
902 \draw (0.5,3.5) node {\large$\star$}; |
853 \draw (1.5,2.5) node {\large$\star$}; |
903 \draw (1.5,2.5) node {\large$\star$}; |
854 \end{tikzpicture} |
904 \end{tikzpicture} |
855 \end{center} |
905 \end{center} |
856 |
906 |
857 \noindent which means states $q_0$ and $q_2$, as well as $q_1$ |
907 \noindent which means states $Q_0$ and $Q_2$, as well as $Q_1$ |
858 and $q_3$ can be merged. This gives the following minimal DFA |
908 and $Q_3$ can be merged. This gives the following minimal DFA |
859 |
909 |
860 \begin{center} |
910 \begin{center} |
861 \begin{tikzpicture}[>=stealth',very thick,auto, |
911 \begin{tikzpicture}[>=stealth',very thick,auto, |
862 every state/.style={minimum size=0pt, |
912 every state/.style={minimum size=0pt, |
863 inner sep=2pt,draw=blue!50,very thick, |
913 inner sep=2pt,draw=blue!50,very thick, |
864 fill=blue!20}] |
914 fill=blue!20}] |
865 \node[state,initial] (q_02) {$q_{0, 2}$}; |
915 \node[state,initial] (Q_02) {$Q_{0, 2}$}; |
866 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
916 \node[state] (Q_13) [right=of Q_02] {$Q_{1, 3}$}; |
867 \node[state, accepting] (q_4) [right=of q_13] |
917 \node[state, accepting] (Q_4) [right=of Q_13] |
868 {$q_{4\phantom{,0}}$}; |
918 {$Q_{4\phantom{,0}}$}; |
869 \path[->] (q_02) edge [bend left] node [above] {$a$} (q_13); |
919 \path[->] (Q_02) edge [bend left] node [above] {$a$} (Q_13); |
870 \path[->] (q_13) edge [bend left] node [below] {$b$} (q_02); |
920 \path[->] (Q_13) edge [bend left] node [below] {$b$} (Q_02); |
871 \path[->] (q_02) edge [loop below] node {$b$} (); |
921 \path[->] (Q_02) edge [loop below] node {$b$} (); |
872 \path[->] (q_13) edge node [above] {$a$} (q_4); |
922 \path[->] (Q_13) edge node [above] {$a$} (Q_4); |
873 \path[->] (q_4) edge [loop above] node {$a, b$} (); |
923 \path[->] (Q_4) edge [loop above] node {$a, b$} (); |
874 \end{tikzpicture} |
924 \end{tikzpicture} |
875 \end{center} |
925 \end{center} |
876 |
926 |
877 \subsubsection*{Regular Languages} |
927 \subsubsection*{Regular Languages} |
878 |
928 |