308
правок
Изменения
→Свойства
Пусть язык <tex>L</tex> распознается [[Детерминированные конечные автоматы|ДКА]] <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle</tex>. Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>|Q|^{|Q|}</tex>.
|proof=
<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}omega</tex> числа: сопоставим вектор <tex>a_{\forall q_i omega} \in Q, q_i \leftrightarrow num(q_i) = i^{|Q|} </tex>. Каждый класс эквивалентности можно закодировать вектором такой, что <tex>aa_{\omega}[i] = j \Leftrightarrow q_i \cdot \omega = q_j </tex> из . Количество различных таких векторов {{---}} <tex>{|Q|}^{|Q|} </tex> чисел, изменяющихся в диапазоне <!--- (поскольку <tex>\forall i = 1..|Q|</tex>. Положим <tex>:\ a[i] = num(q_i \cdot x)1..|Q| </tex> {{) ---}} номер состояния, в которое попадём, если начнём с состояния <tex>q_i. В то же время неэквивалентным словам соответствуют разные </tex>, и пойдём по строке <tex>xa </tex> посимвольно, где <tex>xтогда количество классов эквивалентности также ограничено </tex> {{---}} слово из кодируемого класса эквивалентности. Количество различных векторов данного вида {{---}} <tex>|Q|}^{|Q|}</tex>. Остаётся показать, а количество классов что существует взаимно-однозначное соответствие между нашими классами эквивалентности не превосходит этого значенияи синтаксическими моноидами.Смотрим:Если <br><tex>x \cong y</tex> и <br><tex>uxv \in LLeftrightarrow </tex>, то <br><tex>s \cdot (uyvuxv) = ((s \cdot u) \cdot yx) \cdot v = ((s \cdot u) \cdot xy) \cdot v = s \cdot (uyv) </tex><br><tex> \Leftrightarrow </tex><br><tex> s \cdot (uxv) \in T \Leftrightarrow s \cdot (uyv) \in T</tex>, то есть <br><tex>uyv \in LLeftrightarrow </tex>. Аналогично из <br><tex>uxv \in L \Leftrightarrow uyv \in L</tex> следует <br><tex>uxv \in LLeftrightarrow </tex>. Значит, <br><tex>x \cong y \Rightarrow [[x]] = [[y]]</tex>. Следовательно, размер синтаксического моноида не превосходит количества классов эквивалентности, порождаемых отношением (<tex>\congs </tex>, которое в свою очередь не превосходит <tex>|Q|^{|Q|{---}}</tex>начальное состояние).
}}
