308
правок
Изменения
Заменён первый пример на конечный язык
=== Примеры ===
Здесь будем понимать под <tex> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
# Язык слов над бинарным алфавитом, в которых остаток от деления числа единиц на <tex> 5 </tex> нечётен.#: Пусть <tex> P_k = (0^*1)^k0^* </tex> (слова содержащие <tex> k </tex> единиц). Рассмотрим возможные правые контексты.#::0. <tex> C_L^R(P_5^*) = (P_1 | P_3) P_5^* </tex> #::1. <tex> C_L^R(P_1P_5^*) = (\varepsilon | P_2) P_5^* </tex> #::2. <tex> C_L^R(P_2P_5^*) = (P_4 | P_1) P_5^* </tex> #::3. <tex> C_L^R(P_3P_5^*) = (P_3 | \varepsilon) P_5^* </tex> #::4. <tex> C_L^R(P_4P_5^*) = (P_2 | P_4) P_5^* </tex> #: Таким образом{ 001, 111, автомат построенный на правых контекстах будет содержать 5 состояний.#: <tex> C_L^R(100 \varepsilon) </tex> было рассмотрено в пункте 0 (это начальное состояние).#: <tex> \varepsilon \in C_L^R(X) </tex> в пунктах 1 и 3 (это терминальные состояния).#: При подаче автомату нуля номер текущего состояния не меняется (если у любого правого контекста отрезать слева <tex> 0 </tex>, он не изменится); при подаче единицы номер текущего состояния увеличивается на <tex> 1 </tex> по модулю <tex> 5 } </tex> (правый контекст укорачивается на одну единицу).
# <tex> 0^*11 </tex>
#: Возможные правые контексты (аргументы упорядочены в лексикографическом порядке):
