142
правки
Изменения
Нет описания правки
Если множество двухсторонних контекстов языка конечно, то, очевидно, конечно и множество его правых контекстов, а это значит, что язык регулярный.
<br /><tex>\Rightarrow</tex>:
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>A</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>\langle i,y \rangle \vdash^* \langle u_i(y), \varepsilon \rangle, i = 1,2,\ldots,n</tex> (<tex>n</tex> - число состояний <tex>A</tex>). Если для какого-то слова <tex>z</tex> выполняется <tex>u_i(y) = u_i(z), i = 1,2,\ldots,n</tex>, то <tex>C_L(y) = C_L(z)</tex>.
}}
