Оглавление
Недетерминированный конечный автомат
-
Определение NFA-ε
- NFA-ε – это NFA с ε-переходами, которые позволяют моделировать системы с неопределенными состояниями.
- NFA-ε состоит из конечного множества состояний, входного алфавита, функции перехода, начального состояния и набора принимающих состояний.
-
Формальное определение ε-замыкания
- Для состояния q в NFA-ε, ε-замыкание E(q) представляет собой набор состояний, доступных через ε-переходы.
- Для множества P состояний в NFA-ε, ε-замыкание P определяется как объединение ε-замыканий всех состояний в P.
-
Расширенная функция перехода
- Функция перехода δ∗(q,w) NFA-ε определяет все состояния, которых можно достичь, начав в состоянии q и прочитав строку w.
- Рекурсивное определение δ∗(q,w) учитывает ε-переходы и символы строки w.
-
Пример NFA-ε
- Пример NFA-ε показывает, как описать язык, содержащий четное количество вхождений 0 или 1.
- NFA-ε можно рассматривать как объединение двух DFA, описывающих разные регулярные выражения.
-
Эквивалентность NFA-ε и NFA
- NFA-ε является частным случаем NFA, поэтому необходимо показать, что для каждого NFA-ε существует эквивалентный NFA.
- Для NFA-ε M, эквивалентный NFA M′ определяется с помощью новой функции перехода δ′, которая отличается от исходной δ.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.