308
правок
Изменения
Нет описания правки
Пусть <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>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
}}
=== Примеры ===
Здесь будем понимать под <tex> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
# Язык слов над бинарным алфавитом, в которых число единиц при делении на <tex> 3 </tex> даёт остаток <tex> 2 </tex>.
#: Пусть <tex> P = (0^*10^*10^*10^*)^* </tex> (слова, в которых число единиц кратно 3). Рассмотрим возможные контексты.
#:* <tex> C_L^R(P) = 0^*10^*10^*P </tex>
#:* <tex> C_L^R(0^*10^*P) = 0^*10^*P </tex>
#:* <tex> C_L^R(0^*10^*10^*P) = P </tex>
# <tex> 0^*11 </tex>
#: Возможные контексты (аргументы примерно в лексикографическом порядке):
#:* <tex> C_L^R(0^*) = 0^*(\varepsilon | 1 | 11) </tex>
#:* <tex> C_L^R(0^*1) = 1 </tex>
#:* <tex> C_L^R(0^*10(0|1)^*) = \varnothing </tex>
#:* <tex> C_L^R(0^*11) = \varepsilon </tex>
#:* <tex> C_L^R(0^*11(0|1)^+) = \varnothing </tex>
=== Левый контекст ===
