TVPS_posobie_13_06_2013

Рис. 104. КА для преобразования в СП

Этот автомат имеет четыре состояния (q0, q1, q2, q3) и заключительное состояние – q2.

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

Каждому состоянию qi Q автомата сопоставляется позиция pi в сети Петри, каждая дуга «пересекается» переходом и этот переход помечается тем же символом из А, что и эта дуга.

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

В качестве терминальной разметки берется разметка, при которой имеет фишку только позиция, соответствующая заключительному состоянию.

На Рис. 105 показана помеченная сеть, построенная таким образом по автомату на Рис. 104. Простой анализ способа построения помеченной сети по конечному автомату убеждает в том, что язык, допускаемый автоматом, совпадает с терминальным языком построенной сети.

171

Рис. 105. СП, полученная на основе КА с рис. 106

Однако существуют терминальные языки сетей, не являющиеся регулярными. Например, на Рис. 106 показана помеченная сеть, в которой помечающая функция сопоставляет одному переходу символ открывающей скобки «[», другому – символ закрывающей скобки

«]».

Рис. 106. Скобочная сеть Петри

Для терминальной разметки t= 0 эта сеть порождает терминальный язык, совпадающий с так называемым скобочным языком, слова которого представляют собой «правильно вложенные» последовательности открывающих и закрывающих скобок. Известно, что скобочный язык является контекстно-свободным (и не регулярным) и задается следующей грамматикой:

S0 S0S0, S0 [S0], S0 .

172

Теорема 1. а) La L0, б) La L. Доказательство.

а) Показанная выше возможность построения по КА сети Петри, порождающей тот же язык в качестве терминального, доказывает La L0. Пример со скобочным языком доказывает строгое включение

La L0.

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

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

S0 S0S0, S0 [S0], S0 [S0, S0 .

Теорема 2. Существует терминальный язык, порождаемый помеченной сетью Петри и не являющийся контекстно-свободным.

Доказательство. Достаточно привести пример такой сети.

Известно, что язык {anbnсn| n	0} не является контекстно-свободным.
На рис. 107 показана помеченная сеть,		порождающая этот язык в
качестве терминального для	t=(0, 0, 0, 0,	0, 1).

173

Рис. 107. Помеченная сеть Петри

Теорема 3. Существует контекстно-свободный язык, не порождаемый ни одной (помеченной) сетью Петри.

Доказательство. Рассмотрим в качестве примера контекстносвободный язык L в алфавите {а, b, с}, порождаемый следующей грамматикой:

S0 S0cS0, S0 S, S SS, S aSb, S .

Этот язык обобщает скобочный язык, рассмотренный в доказательстве теоремы 1, если отождествить а с открывающей скобкой [, b с закрывающей скобкой ]. Символы с как бы разделяют правильно вложенные последовательности скобок. Такой язык не порождается никакой помеченной сетью Петри.

Теорема 4. Класс помеченных сетей Петри строго мощнее класса конечных автоматов, не сравним с классом магазинных автоматов и строго менее мощен, чем класс машин Тьюринга.

174

3.10.Некоторые специальные классы КА

Автономный	конечный автомат. Конечный	автомат
V=(A, Q, В, , )	называется автономным, если функции	(z, х) и
(z, х) не зависят существенным образом от переменной х.

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

Рис. 108. Автономный КА

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

Переходная система. Конечный	автомат V=(A, Q, В, , )
называется переходной системой, если	(z, х)=z. Выходные реакции

такого автомата содержат полную информацию о его внутреннем состоянии в текущий момент времени. По существу, переходная система сводится к тройке (A, Q, ), определяющей закон изменения внутренних состояний автомата под действием входных символов.

175

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

Автомат без		потери информации.	Конечный	автомат
V=(A, Q, В,	, ) называется автоматом без потери информации,
если для	каждого	q Q функция (q, х)	определяет	взаимно

однозначное отображение множества А на множество В. При фиксации начального состояния такой автомат осуществляет взаимно однозначное отображение множества А* на множество В*.

Связный КА. Автомат V называется связным, если для соответствующей ему диаграммы Мура соотнесенный неорграф связный (Рис. 109).

Рис. 109. Пример связного КА

Сильно связный КА. Если диаграмма Мура КА есть сильно связный граф, то автомат называется сильно связным. Сильная связность автомата V=(A, Q, В, , ) эквивалентна существованию для любых двух состояний q, q' этого автомата слова А*, такого что q'= (q, ) (Рис. 110).

176

Рис. 110. Пример сильно связного КА

Инициально связный КА. Инициально связный КА – это КА, в котором любая вершина, соответствующей ему диаграммы Мура, достижима из начальной. Другими словами, инициальный КА V=(A, Q, В, , , q) называется инициально связным, если для любого его состояния q' существует слово А*, такое что q'= (q, ).

3.11.Обобщения КА

1группа. Бесконечные КА. Допускаются бесконечные множества состояний, входных и/или выходных символов автомата (некоторые из этих множеств могут быть конечными). Иногда при этом накладываются дополнительные ограничения на функции переходов и выходов. Элементы бесконечных множеств могут быть снабжены структурой.

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

3группа. Видоизменяется само понятие функционирования автомата. При этом либо входная информация поступает не в виде

слов, а в виде «деревьев» (автоматы над термами); либо в

177

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

Автоматы 1 группы

В бесконечных КА множества A, B, Q или часть из них бесконечны. Построение общей теории здесь встречают большие трудности, поэтому рассматривают некоторые специальные подклассы автоматов, чтобы получить нетривиальные результаты. Далее будут рассмотрены автомат Тьюринга, счетчиковый автомат, однородный автомат.

Автомат Тьюринга можно рассматривать как модель устройства, состоящего из конечного автомата V' (головка автомата Тьюринга) и п лент, разбитых на клетки или ячейки (Рис. 111).

Рис. 111. Схема автомата Тьюринга

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

Автомат имеет на каждой из лент «считывающее устройство», расположенное возле некоторой клетки ленты и передающее на вход автомата V' символ, записанный в этой клетке.

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

178

Однородный автомат представляет собой бесконечный абстрактный автомат V=(A, Q, В, , ), у которого A, Q, В множества всевозможных отображений следующего вида:

f: Zk→А',

g:Zk→Q',

h:Zk→В',

где А', Q', В' – некоторые конечные множества, k N – натуральное число, называемое размерностью однородного автомата, Z – множество целых чисел.

Элементы множества Zk естественно интерпретировать как точки k-мерной целочисленной решетки; эти точки называются ячейками однородного автомата V.

Пусть – некоторая ячейка однородного автомата, тогда f( ) описывает входной символ в текущий момент времени t, g( ) – состояние автомата в момент времени t, h( ) – выходной символ в момент времени t.

Состояние ячейки в момент времени t+1 зависит от состояния в момент времени t и входного символа в ячейке , а также в ячейках, принадлежащих некоторой конечной окрестности ячейки .

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

Cчетчиковый автомат – это модификация автомата Тьюринга. Вместо лент в качестве «внешней памяти» используются счетчики, хранящие целые числа. Изменение состояния счетчика заключается в прибавлении к хранящемуся в нем числу 0, +1 либо -1.

179

Автоматы 2 группы

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

Асинхронные автоматы применяются при моделировании ряда систем в технике и биологии. Эти автоматы бывают двух типов.

Асинхронные автоматы первого типа – это конечные

абстрактные автоматы V=(A, Q, В,	, ), у которых	функция
переходов удовлетворяет тождеству	(х, уу)= (х, у), х Q, у	А.

Такие автоматы «реагируют» лишь на изменение входного символа, рассматривая цепочки идущих подряд одинаковых входных символов как один символ.

Асинхронные автоматы второго типа представляют собой

наборы V=(A, Q, В,	, ),	где A, Q,	В – конечные множества, –
функция переходов (	: Q А	Q), – функция выходов такая, что:
		: Q А	B*.

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

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

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

180