Введение в теорию алгоритмов (Поляков В.Н., Скорубский В.И. Основы теории алгоритмов)

1. Введение в теорию алгоритмов (Поляков В.Н., Скорубский В.И. Основы теории алгоритмов)

2. История

3. Определения

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

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

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

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

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

9.

10.

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

12.

13. Утверждение

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

15.

16.

17.

18. ДКА и НДКА

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

19.

1

20.

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

22.

23.

24.

25.

a

26.

27.

a

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

29.

30. Пример

31.

32. Конечные автоматы с выходом

33.

a

34. Записывающие КА

35. Пример