Изменения

|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>\left( C_L^R(\varepsilon) = L \right)</tex>. Вершины, контексты которых содержат <tex>\varepsilon</tex>, должны быть допускающими.