Решение задач на тему: Задание. Рисунки автоматов. Блок схема. Листинг программы. Скриншоты с выполнением примера

Введение

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

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

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

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

В абстрактной теории автоматов важное значение имеют задачи анализа и синтеза автоматов, а на структурном уровне на первый план ставится проблема синтеза автоматов.

Задачи абстрактного анализа и синтеза автоматов противоположны друг другу. Различают канонические и общие задачи абстрактного анализа и синтеза автоматов.

Канонические задачи анализа и синтеза формулируются следующим образом:

) по заданному абстрактному автомату Мили или Мура А найти соответствующее ему каноническое множество событий М,

) по заданному автоматному множеству событий М найти абстрактный автомат Мили или Мура А, каноническое множество событий которого совпадает с М.

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

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

Общие задачи анализа и синтеза автоматов формулируются следующим образом:

) по заданному абстрактному автомату Мили или Мура А найти событие, которое представлено в автомате А любым множеством выходных букв или состоянии автомата;

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

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

Оглавление

- Задание

- Введение

- Рисунки автоматов

- Блок схема

- Листинг программы

- Скриншоты с выполнением примера Заключение

- Список литературы

Список литературы

1. В.Брауэр Введение в теорию конечных автоматов.- М.: Радио и связь, 1999

. Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002

.Савельев А.Я. Прикладная теория цифровых автоматов, 1-е изд. М.: Высшая школа, 2001

. Карпов Ю.Г. Теория автоматов: Учебник / Ю. Г. Карпов. - СПб. : Питер, 2003. - 208с.