Конечные автоматы — Дискретная математика

Определение конечного автомата

— это математическая модель, используемая для описания дискретных динамических систем с конечным числом состояний. Он состоит из множества входных символов, множества внутренних состояний, начального состояния, множества заключительных состояний и функции переходов.

Формальное определение

$A = (Q, \Sigma, \delta, q_0, F)$ , где:

$Q$ — множество внутренних состояний,
$\Sigma$ — алфавит входных символов,
$\delta : Q \times \Sigma \to Q$ — функция переходов,
$q_0 \in Q$ — начальное состояние,
$F \subseteq Q$ — множество заключительных состояний.

Типы конечных автоматов

Существуют два основных типа конечных автоматов:

— у которого для каждой пары текущего состояния и входного символа существует ровно одно следующее состояние.

— у которого для некоторых пар текущего состояния и входного символа может быть несколько возможных следующих состояний.

Пример детерминированного конечного автомата

Рассмотрим простой пример ДКА, распознающего строки вида "aa" или "bb":

$\delta(q_0, a) = q_1,\quad \delta(q_1, a) = q_2,\quad \delta(q_0, b) = q_3,\quad \delta(q_3, b) = q_4$

Здесь $q_0$ — начальное состояние, а $q_2$ и $q_4$ — заключительные.

Регулярные выражения и регулярные языки

Регулярный язык — это язык, который может быть распознан конечным автоматом. Регулярное выражение — это способ компактной записи регулярных языков.

Пример регулярного выражения для языка "aa" или "bb": $(aab|bbb)$ .

Применение конечных автоматов

Конечные автоматы широко применяются в области информационной безопасности, например, при разработке антивирусного ПО, сетевых фильтров и средств защиты от вторжений.

Вопросы для самопроверки

— какой тип конечного автомата является детерминированным?
— как называется язык, распознаваемый конечным автоматом?
$A = (Q, \Sigma, \delta, q_0, F)$ — что обозначает буква $F$ в данном определении конечного автомата?