Двусторонний конечный автомат

• Определение и свойства конечных автоматов

  • Конечный автомат — это машина, которая принимает входные данные и переходит в одно из конечного числа состояний. 
  • Детерминированные конечные автоматы (DFA) имеют однозначные переходы между состояниями. 
  • Недетерминированные конечные автоматы (NFA) могут иметь несколько переходов в зависимости от текущего состояния. 

• Двусторонние конечные автоматы

  • Двусторонние конечные автоматы (2DFA) имеют два конечных маркера и могут перемещаться влево или вправо. 
  • 2DFA эквивалентны односторонним DFA и могут распознавать обычные языки. 
  • 2DFA могут быть более практичными для решения некоторых задач, чем DFA. 

• Двусторонние недетерминированные конечные автоматы

  • 2NFA имеют несколько переходов в одной конфигурации и принимают строку, если принимается хотя бы одно из возможных вычислений. 
  • 2NFA также распознают обычные языки. 

• Двусторонние чередующиеся конечные автоматы

  • 2AFA имеют два типа состояний: экзистенциальные и универсальные. 
  • Экзистенциальные состояния выбирают следующее состояние недетерминированно, а универсальные состояния принимают все возможные вычисления. 

• Сложность преобразования между типами автоматов

  • Преобразование 2DFA в DFA требует экспоненциального увеличения числа состояний. 
  • Преобразование 2NFA в DFA или NFA также требует экспоненциального увеличения состояний. 
  • Проблема точного соотношения между 2NFA и 2DFA остается открытой. 

• Подметальные автоматы и квантовые конечные автоматы

  • Подметальные автоматы — это 2DFA, которые перемещаются по ленте в обоих направлениях. 
  • Двусторонние квантовые конечные автоматы (2QFA) являются обобщением 2DFAs и могут распознавать нерегулярные языки. 

• Двусторонние нажимные автоматы

  • Двусторонние нажимные автоматы (2PDA) могут перемещаться по ленте в любом направлении. 
  • 2DPDA и 2NPDA распознают определенные классы языков, а 2PDA имеют свойства замыкания.