Учебники

Теория автоматов Введение

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

Автомат с конечным числом состояний называется конечным автоматом (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}