Теория алгоритмов

История

Определения

Модели алгоритмов

Модели алгоритмических преобразований

Формализация

КА как модель алгоритма

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

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

Утверждение

Читающие автоматы

ДКА и НДКА
Различают детерминированные (ДКА) и недетерминированные (НДКА) конечные автоматы.
КА называется недетерминированным
(НДКА), если в диаграмме его состояний из одной вершины исходит несколько дуг с одинаковыми символами. Если таких вершин нет, то это ДКА.

1

Преобразование регулярного выражения в КА

a

a

Преобразование КА в регулярное выражение

Пример