64
правки
Изменения
м
→Свойства
{{Лемма
|statement=
Пусть язык <tex>L</tex> распознается [[Детерминированные конечные автоматы|ДКА ]] <tex>A = \langle \Sigma,Q,s,T,\delta \rangle</tex>. Тогда размер его синтаксического моноида <tex>M(L)</tex> не превосходит <tex>|Q|^{|Q|}</tex>.
|proof=
Введём на <tex>\Sigma^*</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=
{{Теорема
|statement=
Пусть <tex>A = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} минимальный [[Детерминированные конечные автоматы|ДКА]], задающий язык <tex>L</tex>. Тогда <tex>M(A)</tex> и <tex>M(L)</tex> изоморфны.
|proof=
Покажем, что <tex>f_x = f_y \Leftrightarrow [[x]] = [[y]]</tex>.
