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

Сложность
Легкий 25%

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

Мы привыкли рисовать автомат детерминированный конечный, изображая состояния кружками, указывая начальное состояние входящей стрелкой, допускающие состояния двойным кружком или исходящей стрелкой, а переход из состояния q в состояние q' считыванием буквы α стрелкой идущие от q к q' и отмеченные α.

детерминированный конечный автомат

Детерминированный конечный автомат A — это тройка (Vt, Q, T), где

  • Vt — словарь автомата;
  • Q — конечное множество состояний автомата;
  • T: Q × Vt → Q — частичное отображение, называемое переходной функцией автомата.

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

Чтение слова

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

Выводим основное свойство полных детерминированных автоматов:

Пусть A = (Vt, Q, T) — полный детерминированный конечный автомат. Тогда для любого слова u ∈ V*ты и для любого состояния q ∈ Q существует единственное состояние q' ∈ Q такое, что q(u)→Aq'.

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

Детерминированный автомат также может быть определен с двумя дополнительными данными:

  • начального состояния i ∈ Q;
  • множества допускающих состояний F ⊆ Q;

Обратите внимание, что начальное состояние и допускающие состояния также могут быть выведены из правил T.

Слово w распознается автоматом, если имеет место так называемое успешное вычисление, исходящее из начального состояния i и заканчивающееся в допускающем состоянии после прочтения слова w. Обозначим через L(A) язык слов, распознаваемых автоматом A. Язык, распознаваемый автоматом, называется распознаваемым. Обозначим через Rec множество распознаваемых языков. Добавление состояния корзины не меняет слова, распознаваемые автоматом.

От языка к автомату

Любой язык, принятый конечным автоматом, является регулярным. Все обычный язык принимается конечным автоматом.

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

  • L — это язык, обозначаемый aba + bab.
  • L - это язык, обозначаемый (аба)* + (баб)*.
  • L = {и € {а, Ь}* такой, что u содержит множитель bbb}.
  • L = {и € {а, Ь}* такое, что u не содержит множителя bbb

детерминированный конечный автомат

Мы можем эффективно преобразовать грамматика регулярной справа в детерминированном конечном автомате и наоборот. Нетерминалы соответствуют состояниям автомата.

Автоматы с распознанными словами

Укажите все слова длины 0, 1, 2, 3 и 4, распознаваемые следующими автоматами. На этот вопрос можно ответить систематически, используя матрицы. Для этого мы представляем автомат (который мы можем видеть как график) по матрице смежности. Таким образом, индексный коэффициент i, j матрицы Mк соответствует словам длины k, распознаваемым автоматом, если начальным состоянием было состояние i, а конечным состоянием — состояние j. Если мы хотим получить слова длины k, распознаваемые нашим автоматом, достаточно умножить матрицу саму на себя.

детерминированный конечный автомат

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

Для автомата A достаточно оценить (1,3) и (1,4) следующих матриц — действительно, распознанные слова начинаются в состоянии 1 и заканчиваются в состоянии 3 или 4:

детерминированный конечный автомат

Слова длины 0: нет; Слова длины 1: б; Слова длины 2: аб + аа + ба; Слова длины 3: аба + абб + ааа + баа; Слова длины 4: абаа + абаб + абба + аббб + аааа + бааа.

Делиться
ru_RURU