Термин «автоматы» происходит от греческого слова «αὐτόματα», что означает «самодействующий». Автомат (множественные числа автоматов) – это абстрактное самоходное вычислительное устройство, которое автоматически выполняет заданную последовательность операций.
Автомат с конечным числом состояний называется конечным автоматом (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}