Основные понятия. Элементы теории конечных автоматов

Элементы теории конечных автоматов

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

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

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

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

По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. Для автомата Мили функция выхода задает отображение в автомате Мура – отображение а в абстрактом С-автомате выходная функция задается двумя составляющими и

при этом или

Произвольный абстрактный автомат Мили и Мура имеет один входной и один выходной каналы (рис. 7.1а.), С-автомат имеет один вход и два выхода (рис. 7.1б).

Рис.7.1. Схемы дискретных автоматов Мили и Мура - а, и С-автомата – б

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

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

Будем полагать, что абстрактный автомат функционирует в дискретном автоматном времени и переходит из состояния в состояние мгновенно. Если автомат инициальный, то в момент автомат находится в начальном состоянии В момент ,находясь в состоянии ,автомат, получая на входе сигнал в соответствии с функцией выходов выдает в тот же момент выход Одновременно автомат в соответствии с функцией переходов переходит в новое состояние В соответствии с определением абстрактного автомата автомат Мили опишется системой уравнений:

автомат Мура – системой уравнений:

а С-автомат системой уравнений:

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

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

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

В случае светофора дискретный автомат мы получим, если в качестве алфавита состояний примем: -«красный», -«желтый после красного», -«зеленый», -«желтый после зеленого», а выходной алфавит -«горит красный», -«горит желтый», -«горит зеленый».

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

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

При матричном способе автомат представляется либо двумя матрицами (переходов и выходов) либо одной матрицей соответствий.

Матрица выходов в зависимости от типа автомата задает отображение или

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

Состояния	Входные сигналы
x1	x2	x3
S1	S1	S2	S1
S2	S3	S4	S2
S3	S3	S1	S4
S4	S3	S1	S2

Состояния	Входные сигналы
x1	x2
S1	S2	---
S2	---	S4
S3	S3	S1
S4	---	S2

а б

Рис. 7.2. Матрицы переходов для полностью определенного

(а) и частичного (б) автоматов

Матрицы выходов для автоматов Мили, Мура и С-автомата различаются. Для автомата Мили она имеет ту же структуру, что и матрица переходов, только элементы матрицы содержат выходные сигналы, реализуемые парами (рис. 7.3а).

Для полностью определенного автомата Мура матрица выходов строится просто: каждому состоянию автомата приписываются свой выход. Для автомата с алфавитами , матрица выходов дана на рис. 7.3б.

Состояния	Входные сигналы
x1	x2	x3
S1	y1	y1	y2
S2	y3	y3	y3
S3	y2	y1	y3
S4	y2	y1	y3

Состояния	Выходные сигналы
S1	y1
S2	y1
S3	y2
S4	y3

а б

Рис. 7.3. Матрицы выходов автоматов Мили (а) и Мура (б)

Для С-автоматов необходимо формировать две матрицы выходов. Одну, как для автомата Мили, а вторую, как для автомата Мура.

Если автомат Мили частичный, то отсутствующим элементам матрицы переходов должны соответствовать такие же пропуски и в матрице выходов. Так, для случая матрицы переходов рис. 7.2б матрица выходов может иметь вид как на рис. 7.4.

Состояние	Входные сигналы
x1	x2
S1	y2	---
S2	---	y2
S3	y1	---
S4	---	y1

Состояние	Выходные сигналы
S1	y1
S2	---
S3	y2
S4	y3

Рис. 7.4. Матрицы выходов Рис. 7.5. Матрица выходов частичного автомата Мили частичного автомата Мура

Прочерки в матрице выходов в частичном автомате Мура не связаны с прочерками в матрице переходов, так как выходной сигнал зависит только от состояния автомата. Следовательно для автомата Мура с матрицей переходов как на рис. 7.2б может иметь вид как на рис. 7.5.

Объединенные матрицы для автоматов Мили и Мура представлены на рис. 7.6, где левая таблица – для полностью определенного автомата Мили рис. 7.2а и рис. 7.3а, а правая – частичного автомата Мура рис.7.2б и 7.3б.

Состояния	Входные системы	Входные сигналы
S1	S2	---	Y1
S2	---	S4	Y1
S3	S3	S1	Y2
S4	---	S2	Y3

Рис. 7.6. Сдвоенные матрицы автоматов Мили и Мура

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

где причем определяет собой входной сигнал, при котором реализуется переход в состояние, соответствующее столбцу, а выходной сигнал будет равен . Для автомата Мили, соответствующего таблице на рис. 7.6, матрица соединений представлена на рис. 7.7.

	S1	S2	S3	S4
S1			___	___
S2	___
S3		___
S4				___

Рис. 7.7. Матрица соединений для автомата Мили, заданного таблицей рис. 7.6.

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

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

Например, автомат Мили, заданный матрицей на рис. 7.7, представлен графом на рис. 7.8, а автомат Мура из рис. 7.3а - на рис 7.9.

Рис. 7.8. Граф автомата Мили Рис. 7.9. Граф автомата Мура

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

Например, для автомата Мили, представленного на рис. 7.6 аналитическое представление имеет вид.

Автомат

Эквивалентными называют автоматы, индукцирующие одно и то же отображение входных слов во входном алфавите во множество слов в выходном алфавите. Можно произвести преобразование автомата Мура в эквивалентный автомат Мили и наоборот.

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

Синтез любых реальных автоматов осуществляется сначала на абстрактных автоматах. В качестве примера рассмотрим синтез автомата управления переключением светофора при условии, что на вход автомата поступает только сигнал «переключить светофор». Пусть этот сигнал , а его отсутствие - , т.е. входной алфавит . В качестве выходных сигналов примем красный, желтый, зеленый, т.е. Положим, что в начальный момент автомат находится в начальном состоянии Алгоритм работы светофора представим на рис. 7.10, где на рис. 7.10а изображен граф автомата Мили, а на рис. 7.10б – автомат Мура.

а б

Рис. 7.10. Графы автоматов Мили –а и Мура –б,

моделирующие работу светофора

Для определенности полагаем, что для автомата Мура в начальный момент выдается сигнал «вычислить зеленый».Отметим, что для построения автомата потребовалось ввести четыре состояния автомата. Их можно уменьшить, увеличив число входных сигналов автомата, либо расширив возможности памяти по предыстории процесса. В данном примере запоминается только момент выдачи последнего выходного сигнала.

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