Изменения
→Свойства
Пусть <tex>\mathcal{A} = \langle \Sigma,Q,s,T,\delta \rangle</tex> {{---}} минимальный [[Детерминированные конечные автоматы|ДКА]], задающий язык <tex>L</tex>. Тогда <tex>M(\mathcal{A})</tex> и <tex>M(L)</tex> изоморфны.
|proof=
Покажем, что <tex>f_x = f_y \quad \Leftrightarrow \quad [[x]] = [[y]]</tex>.
<tex>\Rightarrow</tex>
<tex>\Leftarrow</tex>
<br/>
Пусть <tex>[[x]] = [[y]]</tex> и <tex>q \in Q</tex>. Тогда <tex>q = s \cdot u</tex> для некоторого слова <tex>u</tex>. Пусть <tex>q_1 = f_x(q) = s \cdot ux</tex> и <tex>q_2 = f_y(q) = s \cdot uy</tex>. Поскольку <tex>[[x]] = [[y]]</tex>, справедливо <tex>uxv \in L \quad \Leftrightarrow \quad uyv \in L</tex>. Следовательно, <tex>q_1 \cdot v \in T \Leftrightarrow q_2 \cdot v \in T</tex>, то есть <tex>q_1</tex> и <tex>q_2</tex> эквивалентны. Значит, <tex>q_1 = q_2</tex>, так как автомат <tex>\mathcal{A}</tex> минимален. То есть, <tex>f_x = f_y</tex>.
}}
