390
правок
Изменения
Добавил см. также
Введём следующее отношение эквивалентности на строках:
<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] = q_j \Leftrightarrow q_i \cdot \omega = q_j </tex>. Количество различных таких векторов {{---}} <tex> {|Q|}^{|Q|} </tex><!--- (поскольку <tex> \forall i = 1..\ldots |Q| :\ a[i] = 1..\ldots |Q| </tex>) --->. В то же время неэквивалентным словам соответствуют разные <tex> a </tex>, тогда количество классов эквивалентности также ограничено <tex> {|Q|}^{|Q|} </tex>.
Остаётся показать, что существует взаимно-однозначное соответствие между нашими классами эквивалентности и синтаксическими моноидами. Смотрим:
Значит, синтаксический моноид <tex>M(L)</tex> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.
== См. также ==
* [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)|Анализ свойств регулярных языков]]
* [[Доказательство нерегулярности языков: лемма о разрастании]]
== Источники информации ==
