308
правок
Изменения
м
→Свойства
Пронумеруем состояния нашего автомата, а также введём на <tex>\Sigma^*</tex> следующее отношение эквивалентности:
<br/><tex>x \cong y \Leftrightarrow \forall q \in Q: q \cdot x = q \cdot y</tex>
<br/>Оценим количество классов, на которые отношение <tex>\cong</tex> разбивает язык <tex>L</tex>. Для этого каждому слову <tex> \omega</tex> сопоставим вектор <tex> a_{\omega} \in Q^{|Q|} </tex> такой, что <tex> a_{\omega}[i] = j q_j \Leftrightarrow q_i \cdot \omega = q_j </tex>. Количество различных таких векторов {{---}} <tex> {|Q|}^{|Q|} </tex><!--- (поскольку <tex> \forall i = 1..|Q| :\ a[i] = 1..|Q| </tex>) --->. В то же время неэквивалентным словам соответствуют разные <tex> a </tex>, тогда количество классов эквивалентности также ограничено <tex> {|Q|}^{|Q|} </tex>.
Остаётся показать, что существует взаимно-однозначное соответствие между нашими классами эквивалентности и синтаксическими моноидами. Смотрим:
