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>. Кроме того, в алгоритме на каждом шаге мы ищем все варианты прохода в финальное состояние)упрощали выражение, чтобы оно было более коротким. В общем случае длина выражения перед упрощением трудно поддается оценке, однако не стоит забывать про этот факт. В случае, если выражение не будет упрощаться, то даже в автомате из трех состояний количество итераций может быть достаточно большимпо приведенной выше формуле итерации, оно, очевидно, с каждой итерацией будет значительно (степенная зависимость) расти.
== См. также ==
