308
правок
Изменения
Нет описания правки
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \Sigma^*\}</tex> его правых контекстов конечно.
|proof=
[[Файл:Автомат и правые контексты 1.png|300px315px|thumb|right|Автомат на правых контекстах. Легенда: <font color=orchit>начальное</font> / <font color=orange>промежуточное</font> / <font color=red>дьявольское</font> / <font color=yelloworange>терминальное</font> состояния; <font color=grey>контекст</font>]]
<tex>\Leftarrow</tex>
<br/>
=== Примеры ===
Здесь будем понимать под <tex> C_L^R(X) = Y </tex> не стандартное отображение множества в множество, а <tex> \forall x \in X :\ C_L^R(x) = Y </tex>. Рассмотрим правые контексты следующих языков:
[[Файл:Автомат и правые контексты 2.png|500px|thumb|right|Автомат к языку <tex> \{ 001, 111, 100 \} </tex>]]
# <tex> \{ 001, 111, 100 \} </tex>
#: Возникающие правые контексты:
#:# <tex> C_L^R(\varepsilon) = \{ 001, 111, 100 \} </tex>
#:# <tex> C_L^R(0) = \{ 01 \} </tex>
#: Допускающие состояния: 4, 7, 9 (в них <tex> \varepsilon \in C_L^R(...) </tex>).
#: Состояние 10 {{---}} [[Детерминированные_конечные_автоматы#допускает|дьявольское]].
#: Всего 7 состояний (именно столько имеем различных контекстов).
[[Файл:Автомат и правые контексты 3.png|350px|thumb|right|Автомат к языку <tex> 0^*11 </tex>]]
# <tex> 0^*11 </tex>
#: Возможные правые контексты (аргументы упорядочены в лексикографическом порядке):
#:# <tex> C_L^R(0^*) = 0^*11 </tex>
#:# <tex> C_L^R(0^*1) = 1 </tex>
