Конечный автомат: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Retimuko (обсуждение | вклад) что это? совершенно не энциклопедический стиль, здесь не блог |
Опечаткка |
||
Строка 32:
</gallery>
Если рассмотреть случай, когда автомат задан следующим образом: <math>M = (V, Q, S, F, \delta)</math>, где <math>S</math> — множество ''начальных состояний'' автомата, такое, что <math>S \subseteq
''Теорема о детерминизации'' утверждает, что для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат (два конечных автомата называют эквивалентными, если их языки совпадают). Однако поскольку количество состояний в эквивалентном ДКА в худшем случае растёт [[Экспоненциальный рост|экспоненциально]] с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, [[конечный автомат с выходом|конечные автоматы с выходом]] в общем случае не поддаются детерминизации.
| |||