Автоматы и автоматные языки

Лемма 2.3.1.Каждый автоматный язык распознаётся некоторым конечным автоматом, не содержащим переходов с метками длины больше единицы и имеющим ровно одно начальное состояние и ровно одно заключительное состояние.

Пример 2.3.2.Рассмотрим язык, заданный конечным автоматом (A, Q, D, I, F), где
A={a, b, c, d}, Q=F=I={1, 2}, D={<1,аb,2>, <2,cd,1>}.

Тот же язык распознаётся конечным автоматом (A, Q’, D’, I’, F’), где Q’={0, 1, 2, 3, 4, 5}, I’={0}, F’={5}, D’={<1,a,3>, <3,b,2>, <2,c,4>, <4,d,1>, <0,e,1>, <0,e,2>, <1,e,5>, <2,e,5>}.

Здесь первые два перехода заменяют старый переход <1,аb,2> и следующие два перехода заменяют старый переход <2,cd,1>. Чтобы обеспечить единственность начального состояния, добавлены переходы <0,e,1> и <0,e,2>. Последние два перехода в D' обеспечивают единственность заключительного состояния.

Лемма 2.3.3 (об устранении пустых переходов).Каждый автоматный язык распознаётся некоторым конечным автоматом, содержащим только переходы с метками длины 1 и имеющим ровно одно начальное состояние.

Доказательство. Согласно лемме 2.3.1 можно предположить, что исходный язык задан конечным автоматом (A, Q, D, I, F), не содержащим переходов с метками длины больше единицы, причём . Построим искомый конечный автомат (A, Q’, D’, I’, F’), положив Q' = Q, I’=I,

D' ={<p, a, r>| aÎA и $ такое qÎQ,что <q, a, r>ÎD и существует путь из р в q с меткой e},

F' = {рÎQ | найдётся такое qÎF, что существует путь из р в q с меткой e}. 

Пример 2.3.4.Пусть a_R=(A, Q, D, I, F), где A={a, b}, Q={1, 2, 3}, I={1}, F={3}, D={<1,а,2>, <2,b,2>, <2,e,3>, <3,а,3>}.

Легко убедиться, что L(a_R)= . Тот же язык распознаётся конечным автоматом (A, Q, D’, I, F’), где F’={2, 3} и D’={<1,a,2>, <2,b,2>, <2,a,3>, <3,a,3>}.

Теорема 2.4.1 (критерий автоматности формального языка).Язык является автоматным тогда и только тогда, когда он праволинейный.

Доказательство. Необходимость (каждый автоматный язык является праволинейным). По леммам 2.3.1 и 2.3.3 без ограничения общности можно предположить, что исходный язык задан конечным автоматом a_R=(A, Q, D, I, F), где и . Положим N=Q, S=q₀ и .

Достаточность (каждый праволинейный язык является автоматным). Без ограничения общности можно предположить, что исходный язык задан праволинейной грамматикой, не содержащей правил вида D®и, где . Положим Q=N, I={S}, и , где . 

Заключение по разделу “Конечные автоматы”

Заметим, что наряду с понятием конечного автомата рассматриваются различные его обобщения и модификации, отражающие те или иные особенности реальных устройств. Для конечного автомата существующие модификации можно разбить на следующие три основные группы. К первой группе относятся автоматы, у которых некоторые из алфавитов A (входной), Q (состояний) или B (выходной) бесконечны, в связи с чем такие автоматы называются бесконечными. Ко второй группе относятся автоматы, у которых вместо выходной и переходной функций F и H допускаются произвольные отношения или случайные функции. Таковы частичные, недетерминированные, вероятностные и другие автоматы. К третьей группе относятся автоматы со специфическими множествами входных объектов. Таковы, например, автоматы с переменной структурой. Существуют автоматы, принадлежащие одновременно разным группам.

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

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

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

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

[1] Началом формирования теории формальных языков следует считать вторую половину 1950-х годов.