Оглавление
- 1 Двусторонний конечный автомат
- 1.1 Определение и свойства конечных автоматов
- 1.2 Двусторонние конечные автоматы
- 1.3 Двусторонние недетерминированные конечные автоматы
- 1.4 Двусторонние чередующиеся конечные автоматы
- 1.5 Сложность преобразования между типами автоматов
- 1.6 Подметальные автоматы и квантовые конечные автоматы
- 1.7 Двусторонние нажимные автоматы
- 1.8 Полный текст статьи:
- 2 Двусторонний конечный автомат — Википедия
Двусторонний конечный автомат
-
Определение и свойства конечных автоматов
- Конечный автомат – это машина, которая принимает входные данные и переходит в одно из конечного числа состояний.
- Детерминированные конечные автоматы (DFA) имеют однозначные переходы между состояниями.
- Недетерминированные конечные автоматы (NFA) могут иметь несколько переходов в зависимости от текущего состояния.
-
Двусторонние конечные автоматы
- Двусторонние конечные автоматы (2DFA) имеют два конечных маркера и могут перемещаться влево или вправо.
- 2DFA эквивалентны односторонним DFA и могут распознавать обычные языки.
- 2DFA могут быть более практичными для решения некоторых задач, чем DFA.
-
Двусторонние недетерминированные конечные автоматы
- 2NFA имеют несколько переходов в одной конфигурации и принимают строку, если принимается хотя бы одно из возможных вычислений.
- 2NFA также распознают обычные языки.
-
Двусторонние чередующиеся конечные автоматы
- 2AFA имеют два типа состояний: экзистенциальные и универсальные.
- Экзистенциальные состояния выбирают следующее состояние недетерминированно, а универсальные состояния принимают все возможные вычисления.
-
Сложность преобразования между типами автоматов
- Преобразование 2DFA в DFA требует экспоненциального увеличения числа состояний.
- Преобразование 2NFA в DFA или NFA также требует экспоненциального увеличения состояний.
- Проблема точного соотношения между 2NFA и 2DFA остается открытой.
-
Подметальные автоматы и квантовые конечные автоматы
- Подметальные автоматы – это 2DFA, которые перемещаются по ленте в обоих направлениях.
- Двусторонние квантовые конечные автоматы (2QFA) являются обобщением 2DFAs и могут распознавать нерегулярные языки.
-
Двусторонние нажимные автоматы
- Двусторонние нажимные автоматы (2PDA) могут перемещаться по ленте в любом направлении.
- 2DPDA и 2NPDA распознают определенные классы языков, а 2PDA имеют свойства замыкания.