- English only

# Lab for Automated Reasoning and Analysis LARA

# 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. |