142
правки
Изменения
Нет описания правки
|proof=
<tex>\Leftarrow</tex>:
Пусть множество правых контекстов языка конечно. Тогда построим распознающий его автомат. Состояний автомата будут соответствовать различным правым контекстам. Переход по некоторому символу из одного состояния в другое строится, если контекст, соответствующий первому состоянию, содержит элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму.
<tex>\Rightarrow</tex>:
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>A</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>u</tex> {{---}} состояние <tex>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>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
