390
правок
Изменения
→Правый контекст
|proof=
[[Файл:Автомат и правые контексты 1.png|315px|thumb|right|Автомат на правых контекстах. Легенда: <font color=orchit>начальное</font> / <font color=orange>промежуточное</font> / <font color=red>дьявольское</font> / <font color=yelloworange>терминальное</font> состояния; <font color=grey>контекст</font>]]
<tex>\Leftarrow</tex>quad
<br/>
:Пусть множество правых контекстов языка конечно. Построим распознающий его автомат. Состояния автомата будут соответствовать различным правым контекстам. Таким образом, каждая вершина автомата соответствует множеству допустимых «продолжений» считанного на данный момент слова. Переход по некоторому символу из одного состояния в другое осуществляется, если контекст, соответствующий первому состоянию, содержит все элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму. Вершина, соответствующая контексту пустого слова, является стартовой (<tex>\left( C_L^R(\varepsilon) = L\right)</tex>). Вершины, контексты которых содержат <tex>\varepsilon</tex>, должны быть допускающими.
:Покажем что полученный автомат допускает в точности указанный язык. Выпишем свойства, которые мы стремились удовлетворить при построении:
:: 1. <tex> u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(xc) \quad \Leftrightarrow leftrightarrow \quad \langle u,c \rangle \vdash \langle v, \varepsilon \rangle </tex>:: 2. <tex> s \quad \leftrightarrow \quad C_L^R(\varepsilon) , </tex>, где <tex> s </tex> {{---}} стартовое состояние.
:: 3. <tex> \varepsilon \in C_L^R(\omega) \quad \Leftrightarrow \quad v \in T \quad ( v \quad \leftrightarrow \quad C_L^R(\omega) ) </tex>
:Из 1 следует
