Изменения

Перейти к: навигация, поиск

Контексты и синтаксические моноиды

232 байта добавлено, 19:42, 25 ноября 2014
Нет описания правки
Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой (<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> {{---}} стартовое состояние.
Положив <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> \langle s,\omega \rangle \vdash^* \langle v, \varepsilon \rangle </tex>, означает, что автомат допускает <tex> \omega </tex>.
<tex>\Rightarrow</tex>
<br/>
Пусть <tex>L</tex> {{---}} регулярный. Тогда В таком случае существует автомат <tex>\mathcal{A}</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть Положим <tex>u</tex> {{---}} такое состояние <tex>\mathcal{A}</tex>, в которое можно перейти из начального по слову <tex>y</tex>. Тогда <tex>C_L^R(y)</tex> совпадает с множеством слов, по которым из состояния <tex>u</tex> можно попасть в допускающее. Причем если по какому-то слову <tex>z</tex> тоже можно перейти из начального состояния в <tex>u</tex>, то <tex>C_L^R(y) = C_L^R(z)</tex>. Наоборот, если <tex>C_L^R(y) = C_L^R(z)</tex>, то состояния, в которые можно перейти по словам <tex>y</tex> и <tex>z</tex>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
}}
|proof=
<tex>\Leftarrow</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 \} | = |Q|^2 </tex>, получаем <tex> | \{ C_L(y) \mid y \in \Sigma^* \} | \leqslant 2^{|Q|^2} </tex>, то есть множество контекстов конечно.
}}
308
правок

Навигация