Differences

This shows you the differences between two versions of the page.

--- minimization_of_state_machines [2008/09/20 18:01]
vkuncak
+++ minimization_of_state_machines [2008/09/24 09:58]
vkuncak
@@ Line 7: / Line 7: @@
 This is the process of //minimization// of $M$.
+  * an easy case of minimizing size of 'generated code' in compiler
 We say that state machine $M$ distinguishes strings $w$ and $w'$ iff it is not the case that ($w \in L(M)$ iff $w' \in L(M)$).
 ==== Minimization Algorithm ====
@@ Line 31: / Line 33: @@
 Observe that
-  - if $q \in F$ and $q' \notin F$ then $q$ and $q'$ are $\epsilon$-non-equivalent.
+  - if $q \in F$ and $q' \notin F$ then $q$ and $q'$ are $\epsilon$-non-equivalent
-  - if $q$ and $q'$ are $w$-non-equivalent and we have $\delta(r,a)=q$, $\delta(r',a)=q'$ for some symbol $a \in \Sigma$, then $r$ and $r'$ are $aw$-non-equivalent.
+  - if $q$ and $q'$ are $w$-non-equivalent and we have $\delta(r,a)=q$, $\delta(r',a)=q'$ for some symbol $a \in \Sigma$, then $r$ and $r'$ are $aw$-non-equivalent
+  - conversely, if $r$ and $r'$ are $w'$-non-equivalent and $w$ is not an empty string, then for $w'=aw$ the states $\delta(r,a)$ and $\delta(r',a)$ are $w$-non-equivalent
-These two observations lead to an iterative algorithm for computing non-equivalence relation $\nu$
+These observations lead to an iterative algorithm for computing non-equivalence relation $\nu$
   - initially put $\nu = (Q \cap F) \times (Q \setminus F)$  (only final and non-final states are initially non-equivalent)
   - repeat until no more changes: if $(r,r') \notin \nu$ and there is $a \in \Sigma$ such that $(\delta(r,a),\delta(r',a)) \in \nu$, then
@@ Line 58: / Line 61: @@
 Consequently, $Q^2 \setminus \nu$ is the equivalence relation.  From the definition of this equivalence it follows that if two states are equivalent, then so is the result of applying $\delta$ to them.  Therefore, we have obtained a well-defined deterministic automaton.
 ==== Minimality of Constructed Automaton ====
-Note that if two states are non-equivalent, there is $w$ such that states $\delta(q_0,s_q w)$ and $\delta(q_0,s_{q'} w)$ have different acceptance, so $M$ distinguishes $s_q w$ and $s_{q'}w$.  Now, if we take any other state machine  $M' = (\Sigma,Q',\delta',q'_0,F')$ with $L(M')=L(M)$, it means that $\delta'(q'_0,s_q) \neq \delta'(q'_0,s_{q'})$, otherwise $M'$ would not distinguish $s_q w$ and $s_{q'} w$.  So, if there are $K$ pairwise non-equivalent states in $M$, then a minimal finite state machine for $L(M)$ must have at least $K$ states.  Note that if the algorithm constructs a state machine with $K$ states, it means that $Q^2 \setminus \tau$ had $K$ equivalence relations, which means that there exist $K$ non-equivalent states.  Therefore, any other deterministic machine will have at least $K$ states, proving that the constructed machine is minimal.
+Note that if two distinct states are non-equivalent, there is $w$ such that states $\delta(q_0,s_q w)$ and $\delta(q_0,s_{q'} w)$ have different acceptance, so $M$ distinguishes $s_q w$ and $s_{q'}w$.  Now, if we take any other state machine  $M' = (\Sigma,Q',\delta',q'_0,F')$ with $L(M')=L(M)$, it means that $\delta'(q'_0,s_q) \neq \delta'(q'_0,s_{q'})$, otherwise $M'$ would not distinguish $s_q w$ and $s_{q'} w$.  So, if there are $K$ pairwise non-equivalent states in $M$, then a minimal finite state machine for $L(M)$ must have at least $K$ states.  Note that if the algorithm constructs a state machine with $K$ states, it means that $Q^2 \setminus \tau$ had $K$ equivalence relations, which means that there exist $K$ non-equivalent states.  Therefore, any other deterministic machine will have at least $K$ states, proving that the constructed machine is minimal.
+=== Example ===
+Construct automaton recognizing
+  * language {=,<nowiki><=</nowiki>}
+  * language {=,<=,<nowiki>==</nowiki>}
+Minimize the automaton.