Lab for Automated Reasoning and Analysis 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.
 
minimization_of_state_machines.txt · Last modified: 2015/04/21 17:32 (external edit)
 
© EPFL 2018 - Legal notice