Изменения

Перейти к: навигация, поиск

Контексты и синтаксические моноиды

1325 байт добавлено, 18:51, 17 ноября 2014
Примеры
=== Примеры ===
Здесь будем понимать под <tex> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
# Язык слов над бинарным алфавитом, в которых число остаток от деления числа единиц при делении на <tex> 3 </tex> даёт остаток <tex> 2 5 </tex>нечётен.#: Пусть <tex> P P_k = (0^*10^*101)^*10^*)k0^* </tex> (слова, в которых число содержащие <tex> k </tex> единиц кратно 3). Рассмотрим возможные правые контексты.#:* 0. <tex> C_L^R(PP_5^*) = 0(P_1 | P_3) P_5^*10</tex> #:1. <tex> C_L^R(P_1P_5^*10) = (\varepsilon | P_2) P_5^*P </tex> #:* 2. <tex> C_L^R(0P_2P_5^*10) = (P_4 | P_1) P_5^* </tex> #:3. <tex> C_L^R(P_3P_5^*P) = 0^*10(P_3 | \varepsilon) P_5^*P </tex> #:* 4. <tex> C_L^R(0P_4P_5^*10) = (P_2 | P_4) P_5^*10</tex> #: Таким образом, автомат построенный на правых контекстах будет содержать 5 состояний.#: <tex> C_L^R(\varepsilon) </tex> было рассмотрено в пункте 0 (это начальное состояние).#: <tex> \varepsilon \in C_L^*PR(X) </tex> в пунктах 1 и 3 (это терминальные состояния).#: При подаче автомату нуля номер текущего состояния не меняется (если у любого правого контекста отрезать слева <tex> 0 </tex>, он не изменится) = P ; при подаче единицы номер текущего состояния увеличивается на <tex> 1 </tex> по модулю <tex> 5 </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> #: Итого 4 состояния; начальное состояние 1, допускающее 4, состояние 3&5 {{---}} [[Детерминированные_конечные_автоматы#допускает|тупиковое]].
=== Левый контекст ===
308
правок

Навигация