308
правок
Изменения
м
Автомат А -> \mathcal{A}
<tex>\Rightarrow</tex>
<br/>
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>\mathcal{A}</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>u</tex> {{---}} состояние <tex>\mathcal{A}</tex>, в которое можно перейти из начального по слову <tex>y</tex>. Тогда <tex>C_L^R(y)</tex> совпадает с множеством слов, по которым из состояния <tex>u</tex> можно попасть в допускающее. Причем если по какому-то слову <tex>z</tex> тоже можно перейти из начального состояния в <tex>u</tex>, то <tex>C_L^R(y) = C_L^R(z)</tex>. Наоборот, если <tex>C_L^R(y) = C_L^R(z)</tex>, то состояния, в которые можно перейти по словам <tex>y</tex> и <tex>z</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>\mathcal{A}</tex>, распознающий его. Понятно, что для любого слова <tex> xyz </tex>, допускаемого автоматом, существуют <tex> u ,\ v </tex> такие, что <tex> s * x = u ,\ u * y = v ,\ v * z \in T </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,v \in |Q| \} | = |Q|^2 </tex>, получаем <tex> | \{ C_L(y) \mid y \in \Sigma^* \} | \le 2^{|Q|^2} </tex>, то есть множество контекстов конечно.
}}
{{Лемма
|statement=
Пусть язык <tex>L</tex> распознается [[Детерминированные конечные автоматы|ДКА]] <tex>\mathcal{A } = \langle \Sigma,Q,s,T,\delta \rangle</tex>. Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>|Q|^{|Q|}</tex>.
|proof=
Введём операцию <tex> (\cdot) :\ Q \times \Sigma^* \rightarrow Q </tex> со свойством <tex> q \cdot \omega = q' \Leftrightarrow \langle q,\omega \rangle \vdash^* \langle q', \varepsilon \rangle</tex>.
<br/>Также введём на <tex>\Sigma^*</tex> следующее отношение эквивалентности:
<br/><tex>x \cong y \Leftrightarrow \forall q \in Q: q \cdot x = q \cdot y</tex>
<br/>Оценим количество классов, на которые отношение <tex>\cong</tex> разбивает язык <tex>L</tex>. Сопоставим состояниям автомата <tex>\mathcal{A}</tex> числа: <tex>\forall q_i \in Q, q_i \leftrightarrow num(q_i) = i</tex>. Каждый класс эквивалентности можно закодировать вектором <tex>a</tex> из <tex>|Q|</tex> чисел, изменяющихся в диапазоне <tex>1..|Q|</tex>. Положим <tex>a[i] = num(q_i \cdot x)</tex> {{---}} номер состояния, в которое попадём, если начнём с состояния <tex>q_i</tex>, и пойдём по строке <tex>x</tex> посимвольно, где <tex>x</tex> {{---}} слово из кодируемого класса эквивалентности. Количество различных векторов данного вида {{---}} <tex>|Q|^{|Q|}</tex>, а количество классов эквивалентности не превосходит этого значения.
Если <tex>x \cong y</tex> и <tex>uxv \in L</tex>, то <tex>s \cdot (uyv) = ((s \cdot u) \cdot y) \cdot v = ((s \cdot u) \cdot x) \cdot v = s \cdot (uxv) \in T</tex>, то есть <tex>uyv \in L</tex>. Аналогично из <tex>uyv \in L</tex> следует <tex>uxv \in L</tex>. Значит, <tex>x \cong y \Rightarrow [[x]] = [[y]]</tex>. Следовательно, размер синтаксического моноида не превосходит количества классов эквивалентности, порождаемых отношением <tex>\cong</tex>, которое в свою очередь не превосходит <tex>|Q|^{|Q|}</tex>.
}}
Пусть <tex>\mathcal{A } = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} [[Детерминированные конечные автоматы|ДКА]]. Каждое слово <tex>\omega \in \Sigma^*</tex> порождает отображение <tex>f_\omega : Q \rightarrow Q</tex>, определённое следующим образом: <tex>f_\omega(q) = q \cdot \omega</tex>.
{{Определение
|definition=
'''Моноидом переходов''' (англ. ''transition monoid'') <tex>M(\mathcal{A})</tex> называется множество отображений <tex>f_\omega</tex> с операцией композиции. <tex>f_x \cdot f_y = f_{xy}</tex>. Нейтральным элементом в данном моноиде является отображение <tex>f_\varepsilon</tex>.
}}
{{Теорема
|statement=
Пусть <tex>\mathcal{A } = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} минимальный [[Детерминированные конечные автоматы|ДКА]], задающий язык <tex>L</tex>. Тогда <tex>M(\mathcal{A})</tex> и <tex>M(L)</tex> изоморфны.
|proof=
Покажем, что <tex>f_x = f_y \Leftrightarrow [[x]] = [[y]]</tex>.
<tex>\Leftarrow</tex>
<br/>
Пусть <tex>[[x]] = [[y]]</tex> и <tex>q \in Q</tex>. Тогда <tex>q = s \cdot u</tex> для некоторого слова <tex>u</tex>. Пусть <tex>q_1 = f_x(q) = s \cdot ux</tex> и <tex>q_2 = f_y(q) = s \cdot uy</tex>. Поскольку <tex>[[x]] = [[y]]</tex>, справедливо <tex>uxv \in L \Leftrightarrow uyv \in L</tex>. Следовательно, <tex>q_1 \cdot v \in T \Leftrightarrow q_2 \cdot v \in T</tex>, то есть <tex>q_1</tex> и <tex>q_2</tex> эквивалентны. Значит, <tex>q_1 = q_2</tex>, так как автомат <tex>\mathcal{A}</tex> минимален. То есть, <tex>f_x = f_y</tex>.
}}
