173
правки
Изменения
→Переход от автомата Мили к автомату Мура
И так если осуществить следующие преобразования, то получим:
{| class="table" style="margin-left: 20px; border: 0px solid white"
|-
| style="background: white; padding: 5px 70px 5px 0" | Мили
| style="background: white; padding: 5px 70px 5px 0" | Мура
| style="background: white; padding: 5px 0" | Мили
|-
| style="background: white; padding: 5px 70px 5px 0" | <tex>S_{1} \rightarrow</tex>
| style="background: white; padding: 5px 70px 5px 0" | <tex>S_{2} \rightarrow</tex>
| style="background: white; padding: 5px 0" | <tex>S_{3}</tex>
|-
| style="background: white; padding: 5px 70px 5px 0" | 3 состояния
| style="background: white; padding: 5px 70px 5px 0" | 5 состояний
| style="background: white; padding: 5px 0" | 5 состояний
|}
Можно утверждать, что если <tex>S_{1}</tex> эквивалентно <tex>S_{2}</tex>, а <tex>S_{2}</tex> эквивалентно <tex>S_{3}</tex>, то <tex>S_{1}</tex> эквивалентно <tex>S_{3}</tex> (т.е. эквивалентность обладает свойством транзитивности).
Таким образом возникает задача минимизации автоматов, под которой понимается задача нахождения в классе всех эквивалентных автоматов автомата того же типа (Мили или Мура) с минимальным числом состояний.
