• English only

# Differences

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

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.