Недетерминированные и детерминированные конечные автоматы

1.

Алгоритмы и структуры
данных
2022-2023 учебный год
Нестеров Роман Александрович, PhD & Бессмертный Александр Игоревич
Департамент программной инженерии

2.

План
1. Недетерминированные и детерминированные конечные
автоматы
2. Построение регулярного выражения по заданному
конечному автомату
3. Построение конечного автомата по заданному
регулярному выражению
4. Если не удается построить конечный автомат, …

3.

Для каждого
недетерминированного автомата
существует эквивалентный ему
детерминированный автомат

4.

Упражнение – НКА без