Детерминированный конечный автомат
Детерминированный конечный автомат (ДКА, DFA, англ. deterministic finite automaton, DFSA, англ. deterministic finite-state automaton, DFSM англ. deterministic finite-state machine), известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой[1]. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году[2][3].
Рисунок иллюстрирует детерминированный конечный автомат с помощью диаграммы состояний. В этом примере имеется три состояния — S0, S1 и S2 (отражены на рисунке окружностями). Автомат на вход принимает конечную последовательность нулей и единиц. Для каждого состояния существует стрелка перехода, ведущая из состояния в другое состояние как для 0, так и для 1. После чтения символа, ДКА детерминированно переходит из одного состояния в другое, следуя по стрелке перехода. Например, если автомат находится в состоянии S0, а входным символом является 1, то автомат детерминированно переходит в состояние S1. ДКА имеет начальное состояние (графически показывается стрелкой «из ниоткуда»), откуда начинается вычисление, и множество конечных состояний (обозначаемых графически в виде двойной окружности), которые определяют, успешно ли закончились вычисления.
ДКА определяется как абстрактная математическая концепция, но часто реализуется в аппаратном и программном обеспечении для решения специфичных задач. Например, ДКА может моделировать программы, которые решают допустим ли введённый пользователем email адрес.
ДКА распознаёт в точности множество регулярных языков[1], которые, среди прочего, полезны для лексического анализа и сопоставления с образцом. ДКА могут быть построены из недетерминированного конечного автомата (НКА, англ. nondeterministic finite automata, NFAs) с помощью сведения НКА к ДКА[англ.].
Детерминированный конечный автомат является 5-кортежем, состоящим из
