Теория автоматов и формальных языков. Абстрактный синтез

Август 21, 2022

Главная
Математика
Теория автоматов и формальных языков. Абстрактный синтез

Содержание

2. Синтез автомата Абстрактный синтез Структурный синтез Постановка задачи Аппаратная схема Абстрактный синтез Постановка задачи Программная реализация
3. Абстрактный синтез Процедура выравнивания: Дополним входной алфавит пустым символом α, а выходной алфавит – пустым символом
4. Абстрактный синтез Если область определения алфавитного оператора конечна, его можно задать при помощи таблицы соответствия входов
5. Абстрактный синтез Если встречаются неоднозначности, дописываем в конец входных слов символы α, а в начало выходных
6. Абстрактный синтез Если встречаются неоднозначности, дописываем в конец входных слов символы α, а в начало выходных
7. Построение графа автомата Мили Считаем, что заключительным состоянием всегда является состояние начальное состояние. Состояния можем именовать
8. Построение графа автомата Мура Считаем, что заключительным состоянием всегда является состояние начальное состояние. Состояния можем именовать
9. Минимизация автомата Это скучный слайд с терминологией Два абстрактных автомата с общими входным и выходным алфавитами
10. Минимизация автомата Шаг 1: Внесение неопределённости
11. Минимизация автомата Шаг 2: Исключение недостижимых состояний
12. Минимизация автомата Шаг 3: Объединение совместимых состояний
14. Скачать презентацию

Слайд 2

Синтез автомата
Абстрактный
синтез
Структурный
синтез
Постановка
задачи
Аппаратная
схема
Абстрактный
синтез
Постановка
задачи
Программная
реализация
Структурный
синтез

Слайд 3

Абстрактный синтез
Процедура выравнивания:
Дополним входной алфавит пустым символом α, а выходной алфавит

– пустым символом β.

Процедура пополнения:

Полученный оператор будет являться автоматным.

Слайд 4

Абстрактный синтез
Если область определения алфавитного оператора конечна, его можно задать при

помощи таблицы соответствия входов и выходов.

Однозначен для перечисленных слов и сохраняет длину слова

неоднозначен для начальных отрезков слов

Слайд 5

Абстрактный синтез
Если встречаются неоднозначности, дописываем в конец входных слов символы α,

а в начало выходных - символом β.

Слайд 6

Абстрактный синтез
Если встречаются неоднозначности, дописываем в конец входных слов символы α,

а в начало выходных - символом β.

Слайд 7

Построение графа автомата Мили
Считаем, что заключительным состоянием всегда является состояние начальное

состояние.

Состояния можем именовать произвольным образом.

Слайд 8

Построение графа автомата Мура
Считаем, что заключительным состоянием всегда является состояние начальное

состояние.

Состояния можем именовать произвольным образом.

Слайд 9

Минимизация автомата
Это скучный слайд с терминологией
Два абстрактных автомата с общими входным

и выходным алфавитами эквивалентны, их алфавитные операторы имеют одну область определения и совпадают на ней.

Абстрактный синтез завершается нахождением автомата с минимальным числом состояний, эквивалентного заданному автомату или эквивалентно продолжающего заданный частичный автомат.

Частичным называется автомат над некоторым алфавитом, некоторые последовательности которого никогда не подаются на вход автомата.

Говорят, что оператор φ продолжает оператор ψ, если область определения ψ лежит в области определения φ и на области определения ψ оба оператора совпадают.

Слайд 10

Минимизация автомата Шаг 1: Внесение неопределённости

Слайд 11

Минимизация автомата Шаг 2: Исключение недостижимых состояний

Слайд 12

Минимизация автомата Шаг 3: Объединение совместимых состояний