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