308
правок
Изменения
→Свойства
Пусть язык <tex>L</tex> распознается [[Детерминированные конечные автоматы|ДКА]] <tex>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>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>, а количество классов эквивалентности не превосходит этого значения.
