64
правки
Изменения
м
→Свойства
Введём на <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>, а количество классов эквивалентности не превосходит этого значения.
Если <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>.
}}
