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>a</tex> из <tex>|Q|</tex> чисел, изменяющихся в диапазоне <tex>1..|Q|</tex>. Положим <tex>a[i] = num(q_i \cdot 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>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=
