Что такое дискретная математика?

Что может быть дискретно?
Множества, с которыми мы работаем
Шаги некоторого алгоритма
Время

Что такое ДМ?
Логика высказываний
Логика предикатов
Математическая логика
Комбинаторика
Теория алгоритмов
Теория автоматов
Теория графов
Теория игр
Теория кодирования
Логическое программирование
Функциональное программирование

Теория автоматов и формальных языков
Институт Информационных Технологий
ЧелГУ, 2010

Автомат
Автомат
(реализует преобразователь F)
Черный ящик
X
Y
F: X ? Y
Зависит от того, какая информация в данный момент появилась на входе
от того, что происходило раньше

Автомат
Автомат, в зависимости от входных данных Х меняет свое состояние S – текущее состояние хранится в памяти

Автомат
Пример реализация автомата
Действия – выходные сигналы:
Входные данные:
2,5 - оценки
состояния
Реализация:
программная
аппаратная

Автомат
Пример програмной реализация автомата

Автомат
Пример аппаратной реализация автомата

Автомат
Рассмотрим механизм управления лифтом. Если всего в здании N этажей, лифт может находится в одном из N состояний:
- возможные состояния
На вход подаются номера этажей, к которым должен поехать лифт:
- этажи здания
Выходными сигналами будем считать расстояния, которые должен проехать лифт:
При этом множество возможных значений w(t) конечно и определяется наборам возможных входных значений и множеством этажей.

Автомат
Это скучный слайд с терминологией
- входной алфавит
- выходной алфавит
- набор внутренних состояний
- дискретные моменты времени
- состояние автомата в начальный момент времени
- состояние автомата в момент времени i.
Автомат – математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных.

Алфавитный оператор
Это скучный слайд с терминологией
Последовательности входных букв:
называются входными словами.
На вход автомату может подаваться любое слово из множества допустимы слов.
Каждое допустимое входное слово:
вызывает появление выходного слова:
Длины соответствующих входных и выходных слов равны между собой.
- алфавитный оператор, индуцированный автоматом A.
- множество допустимых входных слов
- множество выходных слов

Функции переходов и выходов
Это скучный слайд с терминологией
- функция переходов, если:
- функция выходов, если:
При помощи задания начального состояния a(0) и функций перехода и выхода λ и δ можно для любого входного слова p определить выходное слово q.

Автоматы Мили и Мура
Это скучный слайд с терминологией
Автомат Мили:
Автомат Мура:
Автомат Мура всегда сводится к автомату Мили:
Символ на выходе зависит только от текущего состояния автомата
Символ на выходе зависит от символа на входе автомата и состояния автомата в предыдущий момент времени

Автомат Мили
Это скучный слайд с терминологией

Автомат Мили
Это скучный слайд с терминологией

Автомат Мура
Это скучный слайд с терминологией

Автомат Мура
Это скучный слайд с терминологией

Автоматы Мили и Мура
Автомат Мура
Автомат Мили
Из автомата Мура можно получить эквивалентный автомат Мили
Слайд 11

Автоматы Мили и Мура
Автомат Мили
Из автомата Мили можно получить эквивалентный автомат Мура
Автомат Мура
Каждое состояние s автомата Мили расщепляется на несколько эквивалентных состояний, с каждым из которых связан один из выхдных символов

Автомат Мили
Из автомата Мили можно получить эквивалентный автомат Мура
Автомат Мура
Автоматы Мили и Мура
Каждое состояние s автомата Мили расщепляется на несколько эквивалентных состояний, с каждым из которых связан один из выхдных символов
В состоянии q мы можем находиться, имея на выходе 0 или 1, значит будет 2 состояния q0 и q1

Условия «автоматности» оператора
Это скучный слайд с терминологией
- алфавитный оператор
1
осуществляет однозначное отображение из P в Q.
2
Если P содержит слово p, то P содержит и все начальные отрезки слова p, включая пустое слово.
3
сохраняет длину слова.
4
Такой оператор называется автоматным оператором.

Теория автоматов
Это скучный слайд с терминологией
Теория автоматов
Состав теории
Абстрактная теория
Математический аппарат теории автоматов, представляет связь с алгеброй и логикой.
Структурная теория
Описывает способы реализации автомата при помощи заданного набора элементов.
Автоматы, рассматриваемые безотносительно их структуры, принято абстрактными автоматами.
Абстрактный автомат задаётся своим входным алфавитом, выходным алфавитом, множеством состояний и автоматным оператором.

Теория автоматов и формальных языков
Приложения теории автоматов
Институт Информационных Технологий
ЧелГУ, 2010

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

Распознаватель правильного идентификатора
Правильным идентификатором называется последовательность букв, цифр и символа подчёркивания, начинающаяся с буквы или символа подчёркивания.
Пусть реализованы функции:
int isLetter(char ch);
int isDigit(char ch);
int isSmall(char ch);
_a123
Var75
my_value
Правильные идентификаторы

Распознаватель правильного идентификатора
Правильным идентификатором называется последовательность букв, цифр и символа подчёркивания, начинающаяся с буквы или символа подчёркивания.
Пусть реализованы функции:
int isLetter(char ch);
int isDigit(char ch);
int isSmall(char ch);
Достаточно функций:
int isLetterOrSmall(char ch);
int isDigit(char ch);