Конечные автоматы

dlyachainikov.ru · Дискретная математика

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

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

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

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

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

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

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

$\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$

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

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

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

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

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

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

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

A = (Q, \Sigma, \delta, q_0, F)

, где:

Q

— множество внутренних состояний,

\Sigma

— алфавит входных символов,

\delta : Q \times \Sigma \to Q

— функция переходов,

q_0 \in Q

— начальное состояние,

F \subseteq Q

— множество заключительных состояний.

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

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

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

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

ДКА — какой тип конечного автомата является детерминированным?

регулярный — как называется язык, распознаваемый конечным автоматом?

A = (Q, \Sigma, \delta, q_0, F)

— что обозначает буква

F

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