С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие



страница1/7
Дата22.12.2012
Размер1.05 Mb.
ТипУчебное пособие
  1   2   3   4   5   6   7



С. В. ТЮРИН

ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ
(Часть 1)
УЧЕБНОЕ ПОСОБИЕ

ВОРОНЕЖ 2002


МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ

ФЕДЕРАЦИИ

Воронежский государственный технический университет


Международный институт компьютерных технологий

ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ

(Часть 1)

Учебное пособие



Воронеж 2002


УДК 519.713(075)
Тюрин С.В. Элементы теории автоматов (Часть 1): Учебное пособие. Воронеж: Воронеж. гос. техн. ун-т, 2002. 98 с.
Рассматриваются основные задачи теории автоматов; различные словесные определения автоматов и их формальная классификация; математические и структурные модели типовых автоматов; способы задания абстрактных и структурных автоматов; вопросы минимизации абстрактных автоматов.

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

Учебное пособие предназначено для студентов технических вузов, обучающихся по специальности 220100 "Вычислительные машины, комплексы, системы и сети".

Учебное пособие подготовлено на магнитном носителе в текстовом редакторе MS WORD 97.0 и содержится в файле "Элементы ТА.doc).
Табл. 16. Ил. 35. Библиогр.: 21 назв.
Научный редактор д-р техн. наук С.Л. Подвальный
Рецензенты: кафедра автоматизированных систем управле- ния Военного института радиоэлектроники (начальник кафедры канд. техн. наук М.И. Чурсин);
д-р техн. наук Н.И.Баранников

Издается по решению редакционно-издательского совета Воронежского государственного технического университета.
© Тюрин С.В., 2002
© Оформление. Воронежский государственный технический университет, 2002

ВВЕДЕНИЕ
Объектами профессиональной деятельности инженеров по специальности 220100 "Вычислительные машины, комплексы, системы и сети" являются "способы и методы проектирования, производства и эксплуатации аппаратных и программных средств вычислительной техники, применяемых в различных областях" [Государственный образовательный стандарт высшего профессионального образования. - М:, 1995г.].

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

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

У
3

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

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

Глава 1. Становление теории автоматов и ее основные задачи


    1. Взаимосвязь теории автоматов и других научно-технических направлений


Теория автоматов является разделом теории управляющих систем, изучающим математические и структурные модели преобразователей дискретной информации, которые и называют автоматами [1], [2]. С определенной точки зрения такими преобразователями являются как материальные объекты (вычислительные машины, живые организмы и т.п.), так и абстрактные системы (математические машины, аксиоматические теории и т.п.).

Теория автоматов возникла в середине ХХ века в связи с изучением конечных автоматов.

Понятие конечного автомата сформировалось в свою очередь с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных и гипотетических дискретных объектов и процессов. Такие попытки были впервые предприняты зарубежными учеными У. Мак-Каллоком, У. Питсом (1943г.), С.К. Клини (1951г.), А. Берксом и Райтом (1954г.) и др.

Характерной особенностью такого математического описания является дискретность соответствующих математических моделей и конечность областей значений параметров моделей, что и приводит к понятию конечного автомата. При этом внешние воздействия, реакции (выходные воздействия) и состояния автомата рассматриваются как буквы трех алфавитов, которые соответственно называют входным алфавитом, выходным алфавитом и алфавитом состояний (иногда говорят, алфавитом внутренних состояний). Тогда описать работу автомата можно некоторыми законами преобразования букв (слов) входного алфавита в буквы (слова) выходного алфавита. Для формализации таких законов преобразования необходимо и достаточно задать всего две функции - функцию переходов и функцию выходов, которые вместе отображают пары "состояние - входная буква" в следующее состояние автомата и его выходную букву. Таким образом, в каждый из моментов дискретного времени автомат, находящийся в определенном состоянии, воспринимает входной сигнал - букву входного алфавита, выдает выходной сигнал - букву выходного алфавита, определяемую функцией выходов, и переходит в новое (следующее) состояние, определяемое функцией переходов.

Наряду с конечным автоматам в теории автоматов рассматриваются различные его обобщения и модификации, которые более точно (адекватно) отражают те или иные особенности реальных объектов [1], [2]. Для конечного автомата существующие модификации можно разбить на следующие три основные группы [1].

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

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

К третьей группе относятся автоматы со специфическими множествами входных алфавитов. К такой группе относятся автоматы с переменной структурой, автоматы над термами и т.п.

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

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


    1. Подходы к определению конечного автомата.


Конечный автомат - математическая модель устройства с конечной памятью (числом состояний), преобразующего дискретную информацию. Конечный автомат является одним из важнейших видов управляющих систем. Содержательно конечный автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый из моментов дискретного времени, называемых тактами (или тактовыми моментами), в одном из конечного числа внутренних состояний. По входному каналу в каждый тактовый момент времени в автомат поступают сигналы - буквы входного алфавита. В те же тактовые моменты времени по выходному каналу автомат выдает выходной сигнал - букву выходного алфавита и переходит в новое состояние из разрешенного числа состояний.

В
6
теории автоматов важное значение имеет понятие автоматного времени. Работа автомата рассматривается в определенные моменты времени, продолжительность которых принимается равной нулю. Эта идеализация не соответствует действительности, но весьма удобна при построении математических моделей. Такие моменты времени следуют через дискретные интервалы конечной продолжительности, которые и называют тактами. Совокупность следующих друг за другом тактов и образует автоматное время.

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

По способу организации автоматного времени все автоматы делят на два больших класса: синхронные автоматы и асинхронные автоматы. Для синхронных автоматов моменты времени, в которых фиксируются изменения состояния автомата, задаются специальным устройством - генератором синхронизирующих сигналов (синхросигналов). Генератор формирует синхронизирующие сигналы через определенные промежутки времени, длительность которых может быть постоянной или переменной. В асинхронных автоматах моменты перехода автомата из одного состояния в другое заранее не определены, так как их продолжительность целиком определяется временем переходных процессов, происходящих в автомате.

П
7

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

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

К определению понятия конечного автомата используются два основных подхода: макроподход и микроподход.

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

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

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

Конечный автомат, как разновидность сложной системы, имеет, так называемое, иерархическое строение. Это означает [3], что после того, как будут выявлены элементы системы и установлена структура их отношений (т.е. схема соединений), можно (или нужно) переходить к рассмотрению каждого из найденных элементов в отдельности для определения состава и отношений "микроэлементов" внутри этих элементов. Чтобы в дальнейшем избежать путаницы и неоднозначности, целесообразно условиться, что первичные элементы и схему их соединения будем называть элементами первого уровня и структурой первого уровня. Вторичные элементы (т.е. элементы элементов) и схему их соединения - элементами второго уровня и структурой второго уровня и т.д. При этом естественно считать, что второй уровень глубже (детальнее) первого, третий - глубже (детальнее) второго и т.д. Очевидно, чем глубже модель, т.е. чем больше уровней оригинала она охватывает, тем ближе свойства модели к свойствам оригинала. Одновременно, чем глубже модель, тем сложнее ее формальное описание и тем сложнее с ним оперировать. Поэтому выбор степени детализации модели реального объекта или процесса определяется целями или условиями решаемой задачи.

Достаточно часто бывают весьма полезны модели нулевого уровня, т.е. такие, которые не могут быть расчленены на составные элементы. В кибернетике такая обобщенная модель нулевого уровня получила название "черный ящик" или метод "черного ящика". Это - наивысший уровень абстракции реального объекта или процесса.


    1. Сущность метода "черного ящика".


Понятие "черный ящик" широко используется в науке и технике [4], поэтому целесообразно остановиться на нем подробнее.

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

М
9
етод "черного ящика" используют для изучения поведения сложных систем, т.е. для установления закона их функционирования. Только после нахождения закона функционирования можно создать более или менее удачную гипотезу о внутреннем устройстве "черного ящика" [3]. Это делается путем подачи (мысленной или реальной) различных типов воздействий на входной канал с тем, чтобы элементы "черного ящика" воспринимали эти воздействия и проявляли бы свою реакцию на них путем изменения сигналов (букв) на выходном канале.

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

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


    1. Основные задачи теории автоматов


Т
10
еория автоматов изначально предназначена для ускорения и облегчения процесса разработки и создания разнообразных дискретных автоматов с достаточным для практического использования запасом надежности.

Теория автоматов зарождалась в тот момент времени, когда основным принципом реализации автоматов был аппаратурный [5]. В связи с этим развивались методы синтеза структуры автоматов в том или ином элементном базисе. Под элементным базисом понимается минимально возможный набор элементов, необходимый и достаточный для практической реализации автоматов сколь угодно большой сложности.

С созданием в 1972 году микропроцессорной техники, оперативных запоминающих устройств (ОЗУ) и постоянных запоминающих устройств (ПЗУ) достаточно большого объема появилась возможность программной реализации разнообразных автоматов.

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

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

С
11

12
овременная элементная база позволяет реализовывать автоматы, в которых часть алгоритма реализуется аппаратурно, а другая часть - программно. Для программной реализации широко используются микропроцессорные комплекты больших интегральных схем (МПК БИС). Для аппаратурной реализации используются специальные БИС с программируемой и перепрограммируемой архитектурой, такие как программируемые логические матрицы (ПЛМ), базовые матричные кристаллы (БМК) и т.п. [6].

Большинство задач теории автоматов - общие для основных видов управляющих систем [1]. К ним относятся задачи:

  • классификации автоматов;

  • анализа и синтеза автоматов;

  • способов задания автоматов;

  • полноты элементарных автоматов;

  • минимизации автоматов;

  • эквивалентных преобразований автоматов;

  • эффективного кодирования автоматов.

Задача классификации автоматов необходима для выявления характерных классов автоматов, их свойств, особенностей и возможностей теоретической и практической реализации.

Задача анализа состоит в том, чтобы по заданной структуре автомата описать его поведение (закон функционирования) или по неполным данным об автомате и законе его функционирования установить те или иные свойства автомата.

Задача синтеза состоит в нахождении способов построения автомата с наперед заданным законом функционирования.

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

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

Задача минимизации автоматов сводится к поиску минимальных по сложности аппаратурной или программной реализации алгоритма функционирования автомата.

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

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

Задача кодирования в общем случае сводится к нахождению правил (способов) сопоставления буквам абстрактных алфавитов некоторых двоичных структурных кодов. От того, насколько удачно осуществлено такое сопоставление (кодирование), зависят и сложность автомата, и надежность его работы [7].

Глава 2. Формальная классификация абстрактных автоматов и их математические модели.
2.1 Словесные определения автоматов.
Формализации (представлению в математической форме) любого понятия предшествует попытка словесного выражения (определения) данного понятия. В этой связи представляет интерес проследить трансформацию во времени словесных определений понятия "автомат".

В энциклопедии "Просвещение" 1900 года издания дается следующее определение (определение 1): "Автомат – прибор, помощью внутреннего механизма подражающий действиям живых существ". Из данного определения следует, что автомат - материальный объект (т.к. прибор); внутри этого материального объекта находится некий механизм; этот механизм действует так, что поведение автомата в целом похоже на действия каких - то живых существ. В соответствии с рассмотренным определением попытаемся выяснить: являются ли механические часы автоматом? Часы - материальный объект; внутри часов работает механизм, отсчитывающий время. Но, действиям какого живого существа подражают обыкновенные механические часы? Таким образом, в соответствии с рассмотренным определением обыкновенные механические часы не могут быть названы "автоматом", т.к. они не подражают действиям какого-либо живого существа.

Р
14

13
ассмотрим модификацию механических часов, которые кроме часового механизма снабжены еще дополнительным механизмом. Таким механизмом может быть петушок, кукарекающий каждый раз, когда часы показывают какое-либо определенное время. В таком случае часы, с кукарекающим через определенные интервалы времени петушком, могут быть отнесены, по определению, к автоматам. Но кукарекать петушка можно "заставить" и без часов, которые отмеривают реальное время. Следовательно, действительным автоматом, по определению, является только кукарекающий петушок. А что если внутри кукарекающего петушка будут отсутствовать механические детали? Можно ли в таком случае отнести такого петушка к автоматам?

Как видно, рассмотренное определение автомата несколько противоречиво, и достаточно широкое, так как "живых существ" - огромное множество, включая и человека.

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

В [8] (1963 год) дается следующее определение (определение 2).

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

В [9] (1980 год) еще более уточняется понятие автомата (определение 3).

Автомат (от греческого automatus - самодействующий)

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

  2. в кибернетике: математическая модель устройства (процесса), перерабатывающего дискретную (цифровую) информацию.

В [10] (1988 год) приводится следующее определение (определение 4).

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

  2. Автомат абстрактный – математическая модель автомата по п.1, определяемая заданием трех множеств (входных сигналов, внутренних состояний и выходных сигналов) и двух двуместных функций (переходов и выходов). Функция переходов отображает первые два множества на второе, а функция выходов отображает первые два множества на третье.

  3. Автомат структурный – автомат абстрактный, по п.2, заданный множеством его элементов и схемой их соединения.

Последнее словесное определение дает возможность перейти к формальному определению понятия автомата.

2.2 Формальное определение абстрактного автомата.
Математической моделью дискретного устройства является абстрактный автомат, определяемый как шестикомпонентный кортеж, или вектор [11]:
S = (Z, A ,W, δ, λ, a1), (2.1)

у которого:

Z={z1,…zf…zF} - множество входных сигналов автомата (входной алфавит);

A={a1,…am…aM} - множество состояний автомата (алфавит состояний);

W={w1,…wg…wG} – множество выходных сигналов автомата (выходной алфавит);

δ : A х Z  A – функция переходов автомата, реализующая отображение Dδ A х Z на A. Другими словами, функция δ некоторым парам состояние - входной сигнал (am, zf) ставит в соответствие состояние автомата as = δ (am, zf), as A;

λ : A х Z  W – функция выходов, реализующая отображение D A х Z на W, которая некоторым парам состояние - входной сигнал (am, zf) ставит в соответствие выходной сигнал автомата wg = λ (am, zf);

a1 A – начальное состояния автомата.

П
16

15
од алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв - словом в данном алфавите.

Абстрактный автомат имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,… В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент времени t(0) автомат может находиться в начальном состоянии a(0) = a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t) Z. В соответствии с функцией выходов он выдает в тот же момент времени t букву выходного алфавита w(t) = λ (a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t +1) = δ (a(t), z(t)), причем a(t +1) A, а w(t) W. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W. Иначе, если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2), … - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1), w(2), … - выходное слово. Каждому входному слову соответствует определенное выходное слово, структура которого определяется функциями переходов и выходов.

Таким образом, на уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные слова. Структурной моделью нулевого уровня абстрактного автомата является модель, представленная на рис. 2.1.


Z W

Рис. 2.1. Структурная модель абстрактного автомата

(нулевой уровень)
В том случае, когда отображения D = D = A х Z, автомат называют полностью определенным или полным. Иными словами, у полностью определенного автомата области определения функций δ, λ совпадают с множеством A х Z – множеством всевозможных пар вида (am, zf). У не полностью определенного, или частичного, автомата функции δ или λ определены не для всех пар (am, zf) A х Z.

Состояние частичного автомата, соответствующее паре (am, zf), на котором функция переходов не определена, называют неиспользуемым состоянием автомата. Остальные состояния называют используемыми [5].

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

Чтобы задать конечный автомат S, необходимо описать все компоненты вектора S = (Z, A ,W, δ, λ, a1), т.е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Среди множества состояний может быть выделено начальное состояния автомата a1, в котором автомат находится в момент t = 0.
2.3 Формальная классификация автоматов
  1   2   3   4   5   6   7

Похожие:

С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconА. Г. Рощин, Р. М. Половов
Теория автоматов. Часть II. Автоматы с памятью. Учебное пособие. М.: Мгту га, 2008. –116 с., табл., ил., лит.: 6 наим
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconПрограмма экзамена по "Теории автоматов"
...
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconГ. Е. Хурсевич Элементы теории функций действительной переменной. Мера и интеграл Лебега. Предисловие. Настоящее учебное пособие
Настоящее учебное пособие представляет собой курс лекций по важному разделу теории функций действительной переменной "Мера и интеграл...
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconТеория игр. Примеры и задачи: Учебное пособие / В. П. Невежин. М.: Форум, 2012. 128 с.: 60x90 1/16. (Высшее образование)
Учебное пособие предназначено для студентов, изучающих в рамках Государственного образовательного стандарта такие дисциплины, как...
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconА. В. Гончар Элементы теории вероятностей
Учебное пособие предназначено для студентов, преимущественно экономических специальностей, изучающих теорию вероятностей в рамках...
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconКонспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32
Учебное пособие предназначено для студентов факультета Кибернетики, изучающих на пятом семестре математическую лингвистику и основы...
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconУчебное пособие для студентов, обучающихся по направлению 521500 (080500. 68) «Магистр менеджмента»
Данное учебное пособие посвящено рассмотрению основ теории управления рисками
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconУчебное пособие по подготовке к пгк часть 1
Учебное пособие предназначено для использования в учебном курсе "Информатика" по ряду специальностей и направлений подготовки студентов...
С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconУчебное пособие по дисциплине «Теория автоматов» для студентов специальности 22. 01. 00

С. В. Тюрин элементы теории автоматов (Часть 1) учебное пособие iconУчебное пособие по дисциплине «Теория автоматов» для студентов специальности 22. 01. 00

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org