Изменения

Пусть язык <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> \omega</tex> сопоставим вектор <tex> a_{\omega} \in Q^{|Q|} </tex> такой, что <tex> a_{\omega}[i] = q_j \Leftrightarrow q_i \cdot \omega = q_j </tex>. Количество различных таких векторов {{---}} <tex> {|Q|}^{|Q|} </tex><!--- (поскольку <tex> \forall i = 1..|Q| :\ a[i] = 1..|Q| </tex>) --->. В то же время неэквивалентным словам соответствуют разные <tex> a </tex>, тогда количество классов эквивалентности также ограничено <tex> {|Q|}^{|Q|} </tex>.