Определения
| Определение: |
Состояния [math]u[/math] и [math]v[/math] различимы строкой [math]s[/math] если
- [math] \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle [/math], где [math]t \in T [/math]
- [math] \langle v, s \rangle \vdash^* \langle z, \varepsilon \rangle [/math], где [math]z \notin T [/math]
|
| Определение: |
| Состояния [math]u[/math] и [math]v[/math] эквивалентны, если они неразличимы никакой строкой [math]s[/math]. |
| Теорема: |
Если [math]u[/math] и [math]v[/math], [math]v[/math] и [math]z[/math] эквивалентны, то [math]u[/math] и [math]z[/math] эквивалентны. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]u[/math] и [math]z[/math] неэквивалентны. Тогда [math] \mathcal {9} s[/math], такой, что
- [math] \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle [/math], где [math]t \in T [/math]
- [math] \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle [/math], где [math]t_1 \notin T [/math].
Рассмотрим [math]x[/math], такой, что [math] \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle [/math].
Если [math]x \in T[/math], то [math]v[/math] и [math]z[/math] различимы строкой [math]s[/math]. Противоречие.
Если [math]x \notin T[/math], то [math]u[/math] и [math]v[/math] различимы строкой [math]s[/math]. Противоречие.
Значит, [math]u[/math] и [math]z[/math] эквивалентны. |
| [math]\triangleleft[/math] |
Алгоритм
Основная идея алгоритма разбить состояния на классы эквивалентности — они и будут состояниями минимального автомата.
В таблице размером [math]n \times n[/math], где [math]n[/math] — количество состояний автомата будем помечать неэквивалентные состояния.
Изначально добавим в очередь [math]Q[/math] пары состояний различимых строкой [math] \varepsilon [/math] и пометим их в таблице.
Пока [math]Q[/math] не станет пуста, будем делать следующее:
- Извлечем пару [math] \langle u, v \rangle [/math] из [math]Q[/math].
- Для всех пар [math] \langle t, k \rangle [/math], таких, что [math] \mathcal {9} c \in \Sigma, \langle t, c \rangle \vdash \langle u, \varepsilon \rangle, \langle k, c \rangle \vdash \langle v, \varepsilon \rangle [/math] и пара [math] \langle t, k \rangle[/math] не отмечена в таблице, то отметим ее в таблице и добавим в [math]Q[/math].
За один проход по таблице согласно теореме разбиваем не помеченные состояния на классы эквивалентности.
