Конечные автоматы — это конечный автомат, который принимает на вход строку символов и соответственно изменяет свое состояние. Конечные автоматы — это распознаватель регулярных выражений. Когда строка регулярного выражения подается в конечные автоматы, она меняет свое состояние для каждого литерала. Если входная строка успешно обработана и автоматы достигают своего конечного состояния, она принимается, т. Е. Только что переданная строка считается допустимым токеном языка в руке.
Математическая модель конечных автоматов состоит из:
- Конечный набор состояний (Q)
- Конечный набор входных символов (Σ)
- Одно стартовое состояние (q0)
- Набор конечных состояний (qf)
- Функция перехода (δ)
Функция перехода (δ) отображает конечный набор состояний (Q) в конечный набор входных символов (Σ), Q × Σ ➔ Q
Конечные Автоматы Констракшн
Пусть L (r) регулярный язык, распознаваемый некоторыми конечными автоматами (FA).
-
Состояния : государства ФА представлены кружками. Названия штатов пишутся внутри кружков.
-
Начальное состояние : состояние, с которого начинается автомат, называется начальным состоянием. Стартовое состояние имеет стрелку, направленную на него.
-
Промежуточные состояния : все промежуточные состояния имеют как минимум две стрелки; один указывает на другого, а другой указывает на них.
-
Конечное состояние : если входная строка успешно проанализирована, ожидается, что автоматы находятся в этом состоянии. Конечное состояние представлено двойными кружками. У него может быть любое нечетное количество стрелок, указывающих на него, и четное количество стрелок, указывающих на него. Количество нечетных стрелок на единицу больше четного, то есть нечетное = четное + 1 .
-
Переход : переход из одного состояния в другое происходит, когда на входе найден нужный символ. После перехода автоматы могут либо перейти в следующее состояние, либо остаться в том же состоянии. Перемещение из одного состояния в другое показано в виде направленной стрелки, где стрелки указывают на состояние назначения. Если автоматы остаются в том же состоянии, рисуется стрелка, указывающая из состояния в себя.
Состояния : государства ФА представлены кружками. Названия штатов пишутся внутри кружков.
Начальное состояние : состояние, с которого начинается автомат, называется начальным состоянием. Стартовое состояние имеет стрелку, направленную на него.
Промежуточные состояния : все промежуточные состояния имеют как минимум две стрелки; один указывает на другого, а другой указывает на них.
Конечное состояние : если входная строка успешно проанализирована, ожидается, что автоматы находятся в этом состоянии. Конечное состояние представлено двойными кружками. У него может быть любое нечетное количество стрелок, указывающих на него, и четное количество стрелок, указывающих на него. Количество нечетных стрелок на единицу больше четного, то есть нечетное = четное + 1 .
Переход : переход из одного состояния в другое происходит, когда на входе найден нужный символ. После перехода автоматы могут либо перейти в следующее состояние, либо остаться в том же состоянии. Перемещение из одного состояния в другое показано в виде направленной стрелки, где стрелки указывают на состояние назначения. Если автоматы остаются в том же состоянии, рисуется стрелка, указывающая из состояния в себя.
Пример : мы предполагаем, что FA принимает любые трехзначные двоичные значения, заканчивающиеся цифрой 1. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}