308
правок
Изменения
м
→Примеры
# Язык слов над бинарным алфавитом, в которых остаток от деления числа единиц на <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>
#: Таким образом, автомат построенный на правых контекстах будет содержать 5 состояний.
#: <tex> C_L^R(\varepsilon) </tex> было рассмотрено в пункте 0 (это начальное состояние).
