308
правок
Изменения
м
→Двухсторонний контекст
<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>\mathcal{A}</tex>, распознающий его. Понятно, что для любого слова <tex> xyz </tex>, допускаемого автоматом, существуют <tex> u ,\ v </tex> такие, что <tex> s * \cdot x = u ,\ u * \cdot y = v ,\ v * \cdot z \in T </tex>. Тогда справедливо равенство <tex> C_L(y) = \bigcup\limits_{(u, v) :\ u \cdot y = v} \{ \langle x, z \rangle \mid s * \cdot x = u ,\ v * \cdot z \in T \} </tex>. Учитывая <tex> | \{ (u, v) \mid u,v \in |Q| ,\ u \cdot y = v \} | = |Q| </tex>, получаем <tex> | \{ C_L(y) \mid y \in \Sigma^* \} | \le 2^{|Q|} </tex>, то есть множество контекстов конечно.
}}
