Термин «автоматы» происходит от греческого слова «αὐτόματα», что означает «самодействующий». Автомат (множественные числа автоматов) — это абстрактное самоходное вычислительное устройство, которое автоматически выполняет заданную последовательность операций.
Автомат с конечным числом состояний называется конечным автоматом (FA) или конечным автоматом (FSM).
Формальное определение конечного автомата
Автомат может быть представлен 5-кортежем (Q, ∑, δ, q 0 , F), где —
Q — конечное множество состояний.
∑ — это конечный набор символов, называемый алфавитом автомата.
δ — функция перехода.
q 0 — начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).
F — множество конечных состояний / состояний Q (F ⊆ Q).
Определение . Алфавит — это любой конечный набор символов.
Пример — ∑ = {a, b, c, d} — набор алфавитов, где «a», «b», «c» и «d» — символы .
Определение — Строка — это конечная последовательность символов, взятая из ∑.
Пример — ‘cabcad’ является допустимой строкой в наборе алфавитов ∑ = {a, b, c, d}
Определение — это количество символов, присутствующих в строке. (Обозначается | S | ).
Примеры —
Если S = ’Cabcad’, | S | = 6
Если | S | = 0, это называется пустой строкой (Обозначается через λ или ε )
Определение — звезда Клини, ∑ * , является унарным оператором на множестве символов или строк, ∑ , который дает бесконечный набор всех возможных строк всех возможных длин над ∑, включая λ .
Представление — ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪ ……. где ∑ p — множество всех возможных строк длины p.
Пример — Если ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ……… ..}
Определение — Множество ∑ + является бесконечным множеством всех возможных строк всех возможных длин над ∑, исключая λ.
Представление — ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪ …….
∑ + = ∑ * — {λ}
Пример — Если ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ……… ..}
Определение — язык является подмножеством ∑ * для некоторого алфавита ∑. Это может быть конечным или бесконечным.
Пример — если язык принимает все возможные строки длины 2 за ∑ = {a, b}, то L = {ab, aa, ba, bb}