308
правок
Изменения
м
→Двухсторонний контекст
'''Двухсторонним контекстом''' (англ. ''two-sided context'') <tex>C_L(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{\langle x,z\rangle \mid xyz \in L\}</tex>.
}}
<!-- Заметим, что <tex>C_L(\varepsilon)</tex> состоит из всех пар строк, которые при конкатенации дают слово из языка.-->
{{Лемма
<br />Заметим, что <tex> \{ z \mid \langle \varepsilon, z \rangle \in C_L(y) \} = C_L^R(y) </tex>. Тогда если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.
<br /><tex>\Rightarrow</tex>
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует полный автомат <tex>A</tex>, распознающий его. Каждой паре состояний Понятно, что для любого слова <tex> (u, v) xyz </tex> соответствует какой-то двухсторонний контекст , допускаемого автоматом, существуют <tex> C_L(y) u ,\ v </tex> такойтакие, что <tex> \forall \langle x ,\ z \rangle \in C_L(y) :\ s * x = u ,\ u * y = v ,\ v * z = t \in T </tex> (недостижимые состояния мы не рассматриваем), и для него будет верно <tex> \forall \omega \in \Sigma^* :\ C_L(y) = C_L(\omega) \Rightarrow u * \omega = v </tex>. Поскольку для всех слов <tex> \omega </tex> существует такая пара <tex> (u, v = u * \omega) </tex>, то Тогда справедливо равенство <tex> C_L(y) = \bigcup\limits_{(u, v) :\ u \cdot y = v} \{ \langle x, z \rangle \mid s * x = u ,\ v * z \in T \} </tex>. Учитывая <tex> | \{ (u, v) \mid u * y ,v \in |Q| \} | = v |Q|^2 </tex>,получаем <tex> | \ v { C_L(y) \mid y \in \Sigma^* z \in T } | \le 2^{|Q|^2} </tex>, то есть множество контекстов конечно.
}}
