Переменный конечный автомат
-
Определение и свойства переменного конечного автомата (AFA)
- AFA — это недетерминированный автомат с экзистенциальными и универсальными переходами.
- Экзистенциальные переходы позволяют выбирать из двух состояний, а универсальные переходы имитируют параллельную машину.
- AFA эквивалентен детерминированному конечному автомату и соответствует обычным языкам.
-
Представление и принятие слов
- AFA представлен 5-кортежем, включающим состояния, входные символы, начальное состояние, принимающие состояния и функцию перехода.
- Функция принятия AFA определяет, принимает ли автомат строку, путем индукции по длине строки.
-
Сложность состояния и вычислительная сложность
- Преобразование AFA в эквивалентный DFA требует экспоненциального числа состояний.
- Существует конструкция, которая преобразует AFA в недетерминированный конечный автомат с полиномиальным числом состояний.
-
Проблемы с AFA
- Проблема членства в AFA является P-полной, даже для одноэлементного алфавита.
- Проблемы непустоты, универсальности и эквивалентности для AFA также являются полными.