Изменения
→Правый контекст
Покажем что полученный автомат допускает в точности указанный язык. Выпишем свойства, которые мы стремились удовлетворить при построении:
: 1. <tex> u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad C_L^R(xc) \quad \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 следует
: 1*. <tex> u \quad \leftrightarrow \quad C_L^R(x) ,\ v \quad \leftrightarrow \quad 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 \quad \leftrightarrow \quad C_L^R(\omega) \quad \Leftrightarrow \quad \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>.
