390
правок
Изменения
Добавил см. также
:: <tex>j) C_L^R(111) = \{ \varepsilon \} </tex> <br><br />
:: <tex>k) C_L^R(X) = \varnothing </tex>, где <tex> X </tex> {{---}} множество остальных аргументов. <br><br />
: Начальное состояние {{---}} <tex>a</tex> . Допускающие состояния: <tex>d, g, j</tex> (в них <tex> \varepsilon \in C_L^R(...\ldots) </tex>). Состояние <tex>k</tex> {{---}} [[Детерминированные_конечные_автоматы#допускает|дьявольское]]. Всего 8 состояний (именно столько имеется различных контекстов).
:[[Файл:Автомат и правые контексты 3.png|350px|thumb|right|Автомат к языку <tex> 0^*11 </tex>]]
==== Пример 2 ====
Введём следующее отношение эквивалентности на строках:
<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> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.
== См. также ==
* [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)|Анализ свойств регулярных языков]]
* [[Доказательство нерегулярности языков: лемма о разрастании]]
== Источники информации ==
