Изменения

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

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

870 байт добавлено, 22:36, 19 ноября 2014
Примеры
Здесь будем понимать под <tex> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
# <tex> \{ 001, 111, 100 \} </tex>
#: Возникающие правые контексты:
#:# <tex> C_L^R(\varepsilon) = \{ 001, 111, 100 \} </tex>
#:# <tex> C_L^R(0) = \{ 01 \} </tex>
#:# <tex> C_L^R(00) = \{ 1 \} </tex>
#:# <tex> C_L^R(001) = \{ \varepsilon \} </tex>
#:# <tex> C_L^R(1) = \{ 11, 00 \} </tex>
#:# <tex> C_L^R(10) = \{ 0 \} </tex>
#:# <tex> C_L^R(100) = \{ \varepsilon \} </tex>
#:# <tex> C_L^R(11) = \{ 1 \} </tex>
#:# <tex> C_L^R(111) = \{ \varepsilon \} </tex>
#:# <tex> C_L^R(X) = \varnothing </tex>, где <tex> X </tex> {{---}} множество остальных аргументов.
#: Начальное состояние {{---}} 1 (<tex> C_L^R(\varepsilon) </tex> рассматривалось в нём).
#: Допускающие состояния: 4, 7, 9 (в них <tex> \varepsilon \in C_L^R(...) </tex>).
#: Состояние 10 - [[Детерминированные_конечные_автоматы#допускает|тупиковое]].
# <tex> 0^*11 </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
правок

Навигация