2.2. Конечные детерминированные автоматы

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

Конечный автомат называется конечным детерминированным автоматом, если для каждой вершины А и каждой буквы а в алфавите пометок существует в точности одна стрелка, ведущая из A и помеченная буквой a, и, кроме того, имеется только одна начальная вершина. Заметим, что рассмотренный выше автомат G₂ является конечным детерминированным автоматом.

Лемма 2.3. Язык представим тогда и только тогда, когда он может быть представлен конечным детерминированным автоматом.

Доказательство. Поскольку часть "тогда" утверждения леммы очевидна, покажем, что каждый представимый язык может быть представлен конечным детерминированным автоматом. Рассмотрим язык L = L(G), представленный конечным автоматом G. Наша цель состоит в построении конечного Детерминированного автомата G', такого, что L = L(G'). Метод, который мы собираемся применить - переход к подмножествам,- часто оказывается весьма полезным.

Определим сначала множество вершин автомата G'. Вершины автомата G' будут находиться во взаимно-однозначном соответствии с подмножествами множества вершин автомата G (включая пустое множество). Для простоты вершинами G' будем считать сами указанные выше подмножества. Начальной вершиной G' является множество, состоящее из всех начальных вершин автомата G. Вершина M автомата G' является заключительной в том и только том случае, когда она (как подмножество множества вершин G) содержит какую-либо заключительную вершину автомата G. Алфавит пометок для стрелок автомата G' совпадает с алфавитом пометок для стрелок автомата G. Для каждой вершины M автомата C и каждой пометки a в G' имеется помеченная буквой а стрелка, ведущая из M в вершину {x| в G имеется помеченная а стрелка, ведущая из какого-либо элемента M в x}.

Из этого определения ясно, что G' - конечный детерминированный автомат. Кроме того, L(G) = L(G'), поскольку если в автомате G существует путь из начальной вершины s₀ в заключительную вершину s₁, помеченный словом w, то в автомате G' также существует помеченный словом w путь из начальной вершины в заключительную вершину, содержащую s₁, и обратно. Это следует из самого построения. Отметим, в частности, роль пустого множества ∅ как вершины G', которая оказывается тупиковой вершиной (так сказать, "мусорным ящиком"): раз войдя в нее, ее уже нельзя покинуть.▫

В большинстве случаев конечный детерминированный автомат G', построенный в предыдущем доказательстве, будет излишне громоздким; тот же самый язык может быть представлен автоматом G" с меньшим числом вершин^*. Такой G" с наименьшим числом вершин является единственным (с точностью до изоморфизма) и легко строится по G', см. упр. 2.

^* (Это, однако, имеет место не всегда. Для некоторых языков построенный автомат G' имеет наименьшее возможное число вершин.- Прим. ред.)

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

Теорема 2.4. Для языка L эквивалентны условия:

• (i) L представим;
• (ii) L матрично представим;
• (iii) L представим конечным детерминированным автоматом;
• (iv) L является языком типа 3.

До сих пор мы не объясняли нашу терминологию. Почему некоторые размеченные орграфы называются автоматами? Хотя мы не намерены пускаться в систематическое обсуждение теории автоматов, все же уместно сделать следующие замечания. Пусть дан понимаемый в некотором содержательном смысле конечный детерминированный автомат. Его можно рассматривать как машину с конечным числом внутренних состояний, символически представленных вершинами. Различные метки на стрелках суть разные входные сигналы, или, короче, входы. Орграф описывает поведение машины, показывая, в какое новое состояние она переходит, получая в определенном состоянии определенный входной сигнал. Машина всегда начинает работу в начальном состоянии. Заключительные состояния можно рассматривать как допускающие: если слово w вызывает переход из начального состояния в одно из заключительных, то оно допускается машиной; в противном случае оно отвергается. Поэтому конечные детерминированные автоматы часто называются распознавателями с конечным числом состояний. Вместо орграфа для задания автомата можно использовать таблицу переходов (т. е. двухместную функцию, описывающую переходы состояний).

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

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

Теорема 2.5. Дополнение представимого языка представимо. Существует алгоритм, выясняющий, является ли данный представимый язык (i) пустым, (ii) бесконечным.

Доказательство. Рассмотрим первое утверждение. По теореме 2.4 любой представимый язык L над ∑ может быть представлен конечным цетермированным автоматом G. Очевидно, дополнение к L (т. е. множество слов из ∑*, не принадлежащих L) может быть представлено конечным детерминированным автоматом, полученным из G заменой всех заключительных состояний на незаключительные и наоборот.

Теперь рассмотрим второе утверждение. Если задан конечный автомат G, то несложно выяснить, существует ли путь из какой-либо начальной вершины в какую-либо заключительную, и, следовательно, определить пуст ли язык L(G) или нет. (Более конкретно, мы рассматриваем сначала множество S₀ начальных вершин автомата G, потом множество S₁, состоящее из вершин, к каждой из которых ведет некоторая стрелка из вершины, содержащейся в So, затем множество S₂, состоящее из вершин, к каждой из которых ведет некоторая стрелка из вершины, содержащейся в S₁ и т. д. Процедура завершается, или когда мы достигаем некоторой заключительной вершины, или когда оказывается, что некоторое множество S_i не содержит новых вершин, т. е. вершин, не принадлежащих никакому S_j при j<i.) Вопрос о бесконечности языка L(G) решается аналогичным образом: L(G) бесконечен тогда и только тогда, когда существует путь, ведущий из начальной вершины в заключительную и обладающий следующим дополнительным свойством: этот путь содержит цикл, т. е. подпуть (состоящий хотя бы из одной стрелки), ведущий из некоторой вершины b в ту же самую вершину.

В связи с предыдущим доказательством читателю полезно обратиться к упр. 4.