В предыдущей статье мы говорили об одном из полных базовых понятий лексического анализа: регулярных выражениях. В этой статье мы расширим наши знания о лексическом анализе и поговорим о конечных автоматах - как недетерминированных (NFA), так и детерминированных (DFA). Нам необходимо понять эти концепции, и в следующей статье мы рассмотрим, как преобразовать NFA в DFA.

Концепция конечных автоматов

Прежде чем продолжить, давайте сначала разберемся с самой концепцией конечных автоматов. Конечные автоматы - это, по сути, абстрактная машина - это самая простая машина для распознавания образов. У него есть набор состояний и правил для перехода из одного состояния в другое, но он зависит от заданного входного символа. Мы можем взять абстрактное представление одного:

Формально можно сказать, что конечный автомат состоит из следующих пяти понятий:

  • В: конечный набор состояний - это все-таки КОНЕЧНЫЙ автомат.
  • Σ: набор входных символов - например, мы могли бы принимать только {0,1} как допустимые входные данные.
  • q: начальное состояние - нам нужно знать, с чего мы начинаем!
  • F: набор конечных состояний - хотя мы можем позволить себе начать только с одного места, допустимо иметь несколько конечных состояний.
  • δ: функция перехода - это означает, что нам нужно знать, как наш ввод перемещает нас из одного состояния в другое и какой результат мы получаем.

В общем, конечный автомат можно описать просто с помощью набора: {Q, Σ, q, F, δ}. Затем мы можем разделить конечные автоматы на две категории: детерминированные и недетерминированные конечные автоматы.

Детерминированные конечные автоматы (DFA)

Детерминированные конечные автоматы - это просто подкатегория конечных автоматов. О DFA следует понимать два важных момента:

  • Для определенного входного символа машина переходит только в одно состояние - мы не можем перейти в несколько состояний одновременно для входа.
  • Нулевое (ε) перемещение не разрешено, что означает, что мы не можем изменить состояние без какого-либо входного символа.

Мы можем взять пример, чтобы проиллюстрировать, что может нравиться DFA. Представим, что мы хотим построить график для DFA, представленный:

DFA = {(A, B, C, D, Ø), (0,1), A, D}

Что это значит? Это означает, что у нас есть 5 состояний: A, B, C, D и Ø. Позже мы объясним, что представляет собой Ø в этом сценарии. Наши принятые входные данные - 0 и 1. Наше начальное состояние - A, а наше конечное состояние - D. Затем нам нужно будет определить нашу функцию перехода, δ. Затем давайте представим, что мы хотим принимать только строки, состоящие либо из двух единиц, либо из двух нулей. Итак, допустимые строки: {00, 11}, в то время как все строки в форме {01, 10, 110…} не принимаются.

Как уже говорилось, мы начинаем с состояния A. Затем мы можем перейти в состояние B или C, в зависимости от нашего ввода. Также стало намного яснее, что такое наше состояние «Ø» - это так называемое мертвое состояние. Когда вы вошли в мертвое состояние, вы не можете снова выйти из него. Это становится ясно, если посмотреть на содержащийся в нем цикл - независимо от ввода, вы не можете вернуться в другое состояние. Вы попадаете в мертвое состояние, когда вводите недопустимый ввод. Представим, что вы перешли из состояния A в состояние C, введя ввод 1 - если вы затем получите ввод 0, то вы получите строку «10». Это недопустимая строка, поэтому она никогда не может быть принята для достижения конечного состояния!

Теперь у нас есть DFA, и мы можем определить нашу функцию перехода. Это выглядит так:

Теперь мы можем легко увидеть, какие входы приводят к какому состоянию - например, если мы получаем вход 0 в состоянии A, мы переходим в состояние B.

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

Мы видели определение и пример DFA, теперь мы можем перейти к NFA. Помните два основных правила для DFA об отсутствии ε-перемещений и о том, что мы не можем переходить в несколько состояний одновременно для заданного входа? Забудьте об этом, когда мы говорим о NFA - здесь разрешены и то, и другое.

Давайте в качестве примера построим NFA:

Затем мы можем создать таблицу для функции перехода:

Тогда мы можем сказать, что наша NFA определяется:

NFA = {(A, B, C, D, E), (0, 1, ε), A, C, δ}

Заключение

Мы определили, что такое DFA и NFA, и рассмотрели несколько примеров. Это будет использовано в следующей статье, где мы увидим, как преобразовать NFA в эквивалентный DFA. Позже мы увидим, как мы можем выражать регулярные выражения через них обоих.