Конечным автоматом Агот называется система {Q,X,Y,f,y}, где Q,X,Y – конечные множества, j,y - функции соответствующих типов.
Q={q0, q1, …, qn} – множество внутренних состояний автомата.
X={x1, …, xt} – входной алфавит
Y={y1, …, yt} – выходной алфавит.
Функции j и y имеют следующие типы:
j: Q´X®Q
y: Q´X®Y
Функцию j(qi; xj)=qi’ называют функцией переходов. Функцию y(qi; xj)=yi’’ называют функцией выходов.
Говорят, что автомат Агот распознает (представляет) множество АÌWx, если существует разбиение множества Q всех состояний этого автомата на подмножества Q+ и Q- такие, что Q=Q+ÈQ-, Q+ÇQ-=Æ, причем wÎА ó когда автомат Агот из начального состояния q0 под действием слова w переходит в какое-либо состояние из подмножества Q+. Таким образом wÏА ó если q0 ¾w® q`ÎQ-.
Покажем, что существуют множества, нераспознаваемые никаким конечным автоматом.
Во-первых это следуют из мощностных соображений. Действительно, для любого конечного алфавита Х множество WX бесконечно (счетно). Поэтому множество всех подмножеств AÌWX несчетно. С другой стороны, конечных автоматов имеется лишь счетное множество. Поэтому и множество автоматов, в которых выделены распознающие подмножества Q+ тоже счетно. Следовательно существуют множества, нераспознаваемые автоматами.
Пусть X={x1, …, xn} – конечный алфавит. Регулярным множеством слов в этом алфавите называют всякое множество АÌWХ, которое может быть получено из пустого множества слов Æ, пустого слова L и множеств {x1}, {x2}, …, {xn} путем применения к ним 3 операций (объединение, конкатенация и итерация) в любом количестве и в любой последовательности.
Примеры:
1. Всякое конечное множество регулярно. А={w1, …, wk}. Всякое событие, состоящее из одного слова, получается из однобуквенных событий путем должного числа умножений. Применяя несколько раз операцию объединения получим данное конечное событие А.
2. Множество всех слов WX регулярно. Х={x1, …, xn}. WX={x1Ú…Úxn}.
3. Множество всех слов вида (ab)n регулярно. {ab}.
Примеры тождеств:
(S1S2)S3=S1(S2S3)=S1(S2S3)
S1ÚS2=S2ÚS1
(S1ÚS2)ÚS3=S1Ú(S2ÚS3)
{{S}}={S}.
Теорема
В конечных автоматах представимы любые регулярные события и только они.
Алгоритм синтеза: занумеруем все вхождения каждой из букв алфавита Х в формулу ФS.
Строящийся автомат Агот будет иметь начальное состояние q0 и некоторое число состояний, название каждого из которых есть подмножество нумерованных букв из формулы ФS. Объясним как строится функция переходов автомата Агот. Пусть q=(xi1, xi2, …, xiN), xÎX. Полагаем j(q,0) – множество тех вхождений буквы 0ÎХ в S, которые в соответствии с формулой ФS могут следовать за буквой х, если слово множества S заканчивается либо хi1, либо хi2, …, либо хiN. Заключительными состояниями (образующими в совокупности распознающее подмножество Q+) объявляются те состояния, которые содержат хотя бы одно вхождение какой-либо буквы алфавита Х, которой может заканчиваться одно из слов множества S.
Машина Тьюринга – это абстрактная вычислительная машина, задаваемая следующим образом: она имеет бесконечную (в обе стороны) ленту, разделенную на одинаковые ячейки. Ячейки не нумеруются. В каждой ячейки ленты записывается один из символов конечного алфавита А соответствующей машины. Обычно в алфавит А включается т.н. пустой символ L. А={a0=L, a1, …, ak}. В частности, при вычислении функций на таких машинах, вся лента, кроме конечного ее фрагмента, заполняется символами L. Переработка информации, записанной на ленте, осуществляется т.н. управляющим устройством. Оно в каждый момент времени (которое считается дискретным) «рассматривает» одну из ячеек ленты. УУ в каждый момент находится в одном из конечного множества состояний. Множество состояний Q={q0, …, qn}. Обычно среди состояний выделяют начальное. В нем машина начинает работать. Работа машины описывается ее программой. Программа есть неупорядоченный набор команд. Всякая команда имеет вид: aiqj®ai’qj’m. либо aiqj®стоп. Применение команды первого типа происходит, если УУ в состоянии qj наблюдает символ ai. Тогда на следующем такте в рассматриваемой ячейке символ ai заменяется на ai’, состояние меняется на qj’, и в соответствии со значением m УУ сдвигается на одну ячейку вправо или влево, или не сдвигается вовсе. Под действием команды второго типа машина останавливается. Она останавливается и в случае, если в состоянии qj попадает на символ ai, для которых в программе нет команды с такой левой частью. Никакая программа не содержит двух различных команд с одинаковыми левыми частями. Если машина останавливается после некоторого количества тактов, то результатом ее работы считается слово, состоящее из всех непустых символов, записанных на ленте. Ясно, что некоторые машины при некоторых начальных условиях могут продолжать работу бесконечно. В этом случае считается, что работа машины не дает результата.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.