Differences
This shows you the differences between two versions of the page.
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. |