Детерминированный конечный автомат
В теории вычислений , разделе теоретической информатики , детерминированный конечный автомат ( DFA ), также известный как детерминированный конечный акцептор ( DFA ), детерминированный конечный автомат ( DFSM ) или детерминированный конечный автомат ( DFSA ) — является конечным автоматом , который принимает или отклоняет заданную строку символов, проходя последовательность состояний, однозначно определяемую строкой. [1] Детерминированныйотносится к уникальности прогона вычислений. В поисках простейших моделей для описания конечных автоматов Уоррен МакКаллох и Уолтер Питтс были одними из первых исследователей, которые в 1943 году представили концепцию, аналогичную конечным автоматам. [2] [3]
На рисунке показан детерминированный конечный автомат, использующий диаграмму состояний . В этом примере автомата есть три состояния: S 0 , S 1 и S 2 (обозначены графически кружками). Автомат принимает на вход конечную последовательность нулей и единиц. Для каждого состояния есть стрелка перехода, ведущая к следующему состоянию как для 0, так и для 1. После считывания символа DFA детерминировано переходит из одного состояния в другое, следуя по стрелке перехода. Например, если автомат в данный момент находится в состоянии S 0 и текущий входной символ равен 1, то он детерминировано переходит в состояние S 1 . DFA имеет начальное состояние(обозначается графически стрелкой, идущей из ниоткуда), где начинаются вычисления, и набор состояний принятия (обозначается графически двойным кругом), которые помогают определить, когда вычисление успешно.
DFA определяется как абстрактное математическое понятие, но часто реализуется в аппаратном и программном обеспечении для решения различных конкретных задач, таких как лексический анализ и сопоставление с образцом . Например, DFA может моделировать программное обеспечение, которое решает, являются ли синтаксически действительными вводимые пользователем данные, такие как адреса электронной почты, или нет. [4]
DFA были обобщены на недетерминированные конечные автоматы (NFA) , которые могут иметь несколько стрелок с одной и той же меткой, начинающихся с состояния. Используя метод построения powerset , каждый NFA можно преобразовать в DFA, который распознает тот же язык. DFA, а также NFA точно распознают набор обычных языков . [1]
Пусть w = a 1 a 2 … an — строка над алфавитом Σ . Автомат M принимает строку w , если в Q существует последовательность состояний r 0 , r 1 , …, r n , со следующими условиями:
Другими словами, первое условие говорит о том, что машина запускается в начальном состоянии q 0 . Второе условие говорит, что для каждого символа строки w машина будет переходить из состояния в состояние в соответствии с функцией перехода δ . Последнее условие говорит, что машина принимает w , если последний ввод w заставляет машину остановиться в одном из состояний принятия. В противном случае говорят, что автомат отвергает строку. Набор строк, которые M принимает, является языком , распознаваемым M , и этот язык обозначается L ( M ).
