LARA

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
minimization_of_state_machines [2008/09/24 09:58]
vkuncak
minimization_of_state_machines [2015/04/21 17:32] (current)
Line 21: Line 21:
  
 We wish to merge states $q$ and $q'$ into same group as long as they "​behave the same" on all future strings $w$, i.e.  We wish to merge states $q$ and $q'$ into same group as long as they "​behave the same" on all future strings $w$, i.e. 
-\[+\begin{equation*}
    ​\delta(q,​w) \in F \mbox{ iff } \delta(q',​w) \in F  \ \ \ (*)    ​\delta(q,​w) \in F \mbox{ iff } \delta(q',​w) \in F  \ \ \ (*)
-\]+\end{equation*}
 for all $w$. for all $w$.
  
Line 40: Line 40:
   - initially put $\nu = (Q \cap F) \times (Q \setminus F)$  (only final and non-final states are initially non-equivalent)   - 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    - 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 
-\[+\begin{equation*}
    \nu := \nu \cup \{(r,​r'​)\}    \nu := \nu \cup \{(r,​r'​)\}
-\]+\end{equation*}
  
 === Step 3: Merge States that are not non-equivalent === === Step 3: Merge States that are not non-equivalent ===
Line 61: 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. 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.
 +
  
  
Line 71: Line 72:
 Construct automaton recognizing Construct automaton recognizing
   * language {=,<​nowiki><​=</​nowiki>​}   * language {=,<​nowiki><​=</​nowiki>​}
-  * language {=,<​=,<​nowiki>​==</​nowiki>​}+  * language {=,<​nowiki>​<=</​nowiki>​,<​nowiki>​==</​nowiki>​}
 Minimize the automaton. Minimize the automaton.