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