308
правок
Изменения
Нет описания правки
<br/>
Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой (<tex>C_L^R(\varepsilon) = L</tex>). Вершины, контексты которых содержат <tex>\varepsilon</tex>, должны быть допускающими.
Покажем что полученный автомат допускает в точности указанный язык. По построению выполняется
: 1. <tex> u \leftrightarrow C_L^R(x) ,\ v \leftrightarrow C_L^R(xc) \quad \Leftrightarrow \quad \langle u,c \rangle \vdash \langle v, \varepsilon \rangle </tex>
: 2. <tex> s \leftrightarrow C_L^R(\varepsilon) </tex>, где <tex> s </tex> {{---}} стартовое состояние.
: 3. <tex> \varepsilon \in C_L^R(\omega) \Leftrightarrow v \in T \quad ( v \leftrightarrow C_L^R(\omega) ) </tex>
Из 1 следует
: 1*. <tex> u \leftrightarrow C_L^R(x) ,\ v \leftrightarrow C_L^R(x \omega) \quad \Leftrightarrow \quad \langle u,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>
Положив <tex> s = u </tex> и учтя 2, получим
* <tex> v \leftrightarrow C_L^R(\omega) \Leftrightarrow \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>
В таких условиях (мы фиксируем за состоянием <tex> v </tex> контекст <tex> C_L^R(\omega) </tex>) левая часть 3 равносильна <tex> \omega \in L </tex>, а правая означает, что автомат допускает <tex> \omega </tex>.
<tex>\Rightarrow</tex>
#: Начальное состояние {{---}} 1 (<tex> C_L^R(\varepsilon) </tex> рассматривалось в нём).
#: Допускающие состояния: 4, 7, 9 (в них <tex> \varepsilon \in C_L^R(...) </tex>).
#: Состояние 10 {{- --}} [[Детерминированные_конечные_автоматы#допускает|тупиковоедьявольское]].
# <tex> 0^*11 </tex>
#: Возможные правые контексты (аргументы упорядочены в лексикографическом порядке):
#:# <tex> C_L^R(0^*11) = \varepsilon </tex>
#:# <tex> C_L^R(0^*11(0|1)^+) = \varnothing </tex>
#: Итого 4 состояния; начальное состояние 1, допускающее 4, состояние 3&5 {{---}} тупиковоедьявольское.
=== Левый контекст ===
'''Двухсторонним контекстом''' (англ. ''two-sided context'') <tex>C_L(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{\langle x,z\rangle \mid xyz \in L\}</tex>.
}}
'''Интересный моментЛюбопытное замечание:''' <tex>C_L(\varepsilon)</tex> состоит из всех пар строк, которые при конкатенации дают слово из языка.
<br />Заметим, что <tex> \{ z \mid \langle \varepsilon, z \rangle \in C_L(y) \} = C_L^R(y) </tex>. Тогда если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.
<br /><tex>\Rightarrow</tex>
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует детерминированный автомат <tex>\mathcal{A}</tex>, распознающий его. Понятно, что для любого слова <tex> xyz </tex>, допускаемого автоматом, существуют <tex> u ,\ v </tex> такие, что <tex> s \cdot x = u ,\ u \cdot y = v ,\ v \cdot z \in T </tex>(где <tex> s </tex> {{---}} начальное состояние). Тогда справедливо равенство <tex> C_L(y) = \bigcup\limits_{(u, v) :\ u \cdot y = v} \{ \langle x, z \rangle \mid s \cdot x = u ,\ v \cdot z \in T \} </tex>. Учитывая <tex> | \{ (u, v) \mid u,v \in Q ,\ u \cdot y = v \} | = |Q| </tex>, получаем <tex> | \{ C_L(y) \mid y \in \Sigma^* \} | \leqslant 2^{|Q|} </tex>, то есть множество контекстов конечно.
}}
'''3'''. Язык <tex>L = 0^n1^n</tex> задан над алфавитом <tex>\Sigma = \{0,1\}</tex>. Балансом слова <tex>|\omega|_b</tex> назовём число, равное разности между количеством нулей и единиц, встречающихся в данном слове. Если слово <tex>\omega = uxv</tex> принадлежит языку <tex>L</tex>, то <tex>|x|_b = -(|u|_b + |v|_b)</tex>. Но <tex>|x|_b</tex> может принимать любое целое значение, при том, что <tex>x</tex> имеет непустой двухсторонний контекст. Значит, синтаксический моноид <tex>M(L)</tex> имеет бесконечное количество элементов, что значит, что данный язык не является регулярным.
== Ссылки Источники информации ==
* ''Howard Straubing'' Finite automata, formal logic, and circuit complexity, 1994. ISBN 3-7643-3719-2. {{---}} C. 53.
* ''James A. Anderson'' Automata theory with modern applications, 2006. ISBN 0-521-61324-8. {{---}} С. 72.
* [http://en.wikipedia.org/wiki/Syntactic_monoid Syntactic monoid {{- --}} Wikipedia]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
