Коне́чный автома́т — абстрактный автомат, число возможных внутренних состояний которого конечно.
Существуют различные способы задания алгоритма функционирования конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки элементов некоторых множеств:
M
=
(
V
,
Q
,
q
0
,
F
,
δ
)
{\displaystyle M=(V,Q,q_{0},F,\delta )}
,
где
V
{\displaystyle V}
— входной алфавит (конечное множество входных символов), из которого формируются входные слова, воспринимаемые конечным автоматом;
Q
{\displaystyle Q}
— множество внутренних состояний;
q
0
{\displaystyle q_{0}}
— начальное состояние
(
q
0
∈
Q
)
{\displaystyle (q_{0}\in Q)}
;
F
{\displaystyle F}
— множество заключительных, или конечных состояний
(
F
⊂
Q
)
{\displaystyle (F\subset Q)}
;
δ
{\displaystyle \delta }
— функция переходов, определенная как отображение
δ
:
Q
×
(
V
∪
{
λ
}
)
→
Q
{\displaystyle \delta \colon Q\times (V\cup \{\lambda \})\rightarrow Q}
, такое, что
δ
(
q
,
a
)
=
{
r
:
q
→
a
r
}
{\displaystyle \delta (q,a)=\{r\colon q\,\,{\underset {a}{\to }}\,\,r\}}
, то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).
Принято полагать, что конечный автомат начинает работу в состоянии
q
0
{\displaystyle q_{0}}
, последовательно считывая по одному символу входного слова (цепочки входных символов). Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов.
Читая входную цепочку символов
x
{\displaystyle x}
и делая переходы из состояния в состояние, автомат после прочтения последнего символа входного слова окажется в некотором состоянии
q
′
{\displaystyle q'}
.
Если это состояние является заключительным, то говорят, что автомат допустил слово
x
{\displaystyle x}
.
Конечные автоматы широко используются на практике, например, в синтаксических и лексических анализаторах, тестировании программного обеспечения на основе моделей.
Существуют различные способы задания алгоритма функционирования конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки элементов некоторых множеств:
M
=
(
V
,
Q
,
q
0
,
F
,
δ
)
{\displaystyle M=(V,Q,q_{0},F,\delta )}
,
где
V
{\displaystyle V}
— входной алфавит (конечное множество входных символов), из которого формируются входные слова, воспринимаемые конечным автоматом;
Q
{\displaystyle Q}
— множество внутренних состояний;
q
0
{\displaystyle q_{0}}
— начальное состояние
(
q
0
∈
Q
)
{\displaystyle (q_{0}\in Q)}
;
F
{\displaystyle F}
— множество заключительных, или конечных состояний
(
F
⊂
Q
)
{\displaystyle (F\subset Q)}
;
δ
{\displaystyle \delta }
— функция переходов, определенная как отображение
δ
:
Q
×
(
V
∪
{
λ
}
)
→
Q
{\displaystyle \delta \colon Q\times (V\cup \{\lambda \})\rightarrow Q}
, такое, что
δ
(
q
,
a
)
=
{
r
:
q
→
a
r
}
{\displaystyle \delta (q,a)=\{r\colon q\,\,{\underset {a}{\to }}\,\,r\}}
, то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).
Принято полагать, что конечный автомат начинает работу в состоянии
q
0
{\displaystyle q_{0}}
, последовательно считывая по одному символу входного слова (цепочки входных символов). Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов.
Читая входную цепочку символов
x
{\displaystyle x}
и делая переходы из состояния в состояние, автомат после прочтения последнего символа входного слова окажется в некотором состоянии
q
′
{\displaystyle q'}
.
Если это состояние является заключительным, то говорят, что автомат допустил слово
x
{\displaystyle x}
.
Конечные автоматы широко используются на практике, например, в синтаксических и лексических анализаторах, тестировании программного обеспечения на основе моделей.
Источник: Wipedia.org