317
правок
Изменения
→Пример
{| border="1" class="wikitable" style="width: 300px; height: 250px; float: left;"
!style="background:#41aef0"|Выражение
!style="background:#41aef0"|Упрощенное выражение (после подстановки)
|-
является начальным, а второе {{---}} заключительным. В нашем примере <tex>1</tex> {{---}} начальное состояние, а <tex>2</tex> {{---}} заключительное, поэтому нам нужно лишь выражение <tex>R_{12}^{(1)}</tex>, равное <tex>1^*0(0 + 1)^*</tex>
Отметим, что первый вариант значительно короче. Для решения системы уравнений необходимо выполнить <tex>O(n)</tex> итераций, где <tex>n</tex> {{---}} число вершин. В общем каждом уравнении в худшем случаеможет быть <tex>|\Gamma| \cdot (n - 1)</tex> переменных в правой части {{---}} все возможные переходы по всем возможным состояниям. Теперь, обычно проще решить систему уравненийдля решения вторым вариантом, чем выполнять несколько нам во-первых надо построить массив размера <tex>|\Gamma| \cdot n</tex> для всех переходов из всех состояний и выполнить столько же итераций. Учитывая, что количество итераций увеличивается поскольку самый длинный путь в худшем случае будет проходить по всем переходам из всех вершин с увеличением переходов возвращением в автомате (мы ищем все варианты прохода в терминальное состояние)исходную, которая и будет являться терминальной, то даже есть в автомате из трех состояний количество итераций может быть достаточно большим.итоге сложность <tex>O((|\Gamma| \cdot n)^2)</tex>
== См. также ==
