Теория вычислений. Введение в конечные автоматы

Спойлер
Cкажу cразу, что не буду объяснять слишком формально.

Конечные автоматы (finite-state machine)


Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рас­суждения и легкость программной или аппаратной реализации.

С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.

У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.

Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.

Пример 1
  • По горизонтали вверху находятся возможные входные символы.
  • По вертикали слева находятся текущие возможные состояния.

image

Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ 'a', из состояния 1 в состояние 2, если символ 'b'.


Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

Стартовое состояние — состояние откуда КА начинает свою работу.

Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.

Детерминированные конечные автоматы (deterministic finite automaton)


Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.

Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.

Пример 2
image
Здесь изображена диаграмма переходов для ДКА, визуализация примера 1. Состояние 3 является заключающим. По диаграмме видно, что ДКА принимает цепочку символов только в том случае, если будет последовательность из символов 'a', 'b' и 'c'.

Недетерминированные конечные автоматы (nondeterministic finite automaton)


НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.

Реализация НКА
// Ячейка массива состоящая из: текущее_состояние, считаный_символ, следующее_состояние.
struct state {
	unsigned char current;
	signed char sym; // signed, для обозначения свободного перехода как -1.
	unsigned char next;
};

// Таблица переходов для НКА на примере 2
struct state machine[] = {
	{0, 'a', 1},
	{1, 'a', 1},
	{2, 'a', 1},
	{1, 'b', 2},
	{2, 'c', 3}
};


Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.

Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.

Множества состояний — в один момент времени НКА может находится в нескольких состояниях.

Пример 3
Заключительное состояние обозначается двойным кругом.

image

В стартовом состоянии у нас текущим состоянием является {1}, при входном символе 'b' у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа 'b' текущим состоянием является множество {1, 2}.

Пример 4
Свободным переходом обозначается пунктирной линией.

image

Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии {2, 4}.


Для преобразования НКА в ДКА используется алгоритм Томпсона.
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.

Конечные автоматы с магазинной памятью (pushdown automaton)


Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.

КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).

Удаление символа из стека — при любом переходе решается какой символ вытолкнуть, если на вершине стека не оказалось такого символа, то он и не выталкивается. Так же если символ нужно оставить в стеке, то он добавляется вместе с добавляемыми символами.

Добавление символов в стек — при любом переходе решает какие символы добавить в стек.

Виды:

  • Детерминированные — к нему применяются те же правила как к ДКА к тому же завершает работу только в заключительном состоянии.
  • Недетерминированные — к нему применяются те же правила как к НКА к тому же он может завершать работу в заключительном состоянии или когда стек станет пуст.

Пример 5
Шаблон: входной_символ; удаляемый_символ/добавляемый символ. На дно стека добавляется символ $ для, того, что понять когда он закончился.

image

Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.


ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.

Машина Тьюринга (Turing machine)


Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.

Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.

Пример 6
Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются '_'.

image

Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.

Выполнение:

  1. Если находится в состоянии 1 и прочитан нуль, записать еди­ницу, сдвинуть вправо и перейти в состояние 2.
  2. Если находится в состоянии 1 и прочитана единица, записать нуль, сдвинуть влево и перейти в состояние 1.
  3. Еcли находится в состоянии 1 и прочитан пустой квадратик, записать единицу, сдвинуть вправо и перейти в состояние 2.
  4. Если находится в состоянии 2 и прочитан нуль, записать нуль, сдвинуть вправо и остаться в состояние 2.
  5. Если находится в состоянии 2 и прочитана единица, записать единицу, сдвинуть вправо и остаться в состояние 2.
  6. Если находится в состоянии 2 и прочитать пустой квадратик, записать пустой квадратик, сдвинуть влево и перейти в состоя­ние 3.

ДМТ эквивалентен НМТ, так, что они тоже не различаются.

Универсальная машина Тьюринга (universal Turing machine)


Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.

Недостатки:

  1. Память порождаемой машины не может быть больше, чем у самой УМТ.
  2. Нужно уметь правильно разделять пространство ленты между порождаемой машиной и УМТ, ведь их данные находятся на одной ленте.

На этом введение в автоматы закончено, теперь вы можете продолжить изучать дальнейший материал сами.

Литература:

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 8

    –1
    КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стэка (я понимаю, что память тоже конечна).
    тут не очень понятно, обычный автомат NFA или DFA справляется с задачей разбора неограниченного количества вложенных скобок без всякой памяти.
      0
      тут не очень понятно, обычный автомат NFA или DFA справляется с задачей разбора неограниченного количества вложенных скобок без всякой памяти.

      Нет, не справляется.
        +2
        Да, извиняюсь, что то я прогнал, перепутал конечные автоматы с рекурсивным спуском.
        0
        У КА нет никакой памяти, он не может ничего запоминать, кроме как своего состояния. Можно в принципе сделать таблицу переходов на определенное количество скобок, но опять же оно будет конечно. Примерная реализация habrastorage.org/webt/8l/cq/oi/8lcqoiow02afwvibockefwvqg0c.jpeg
          0
          Да, все верно, у меня просто в голове все в кучу уже смешано, я эти конечные автоматы и парсеры очень часто пишу чисто для разминки )
          0

          Скорее имелось ввиду, что с помощью DFA нельзя определить правильность расстановки скобок, на сколь угодно большом входе.

          +1
          Добавлю свои пять копеек про алгоритм Томпсона. В некоторых случаях нам не нужно строить весь DFA — сразу. К примеру, имеется исходник регулярки и для разбора строки нам нужно: распарсить ее, построить NFA и затем по идее преобразовать его в DFA для разбора. Последний шаг может занять довольно продолжительное время, а потому для экономии времени используется схема при которой DFA строиться лишь для ветки по которой идет разбор, что существенно повышает скорость работы в подобных случаях.
            0
            Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами

            Все вышеперечисленное тоже вполне себе может быть конечным автоматом.

            Only users with full accounts can post comments. Log in, please.