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

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

Определение 10. Конечное множество элементов будем называть словарём, элементы словаря – символами, а последовательности символов словаря – цепочками или предложениями. Множество предложений назовём языком. Язык над словарём V будем обозначать LV, или просто L, если V очевидно.

Пусть V – словарь. Обозначим через V* множество всех возможных цепочек, составленных из символов словаря V. Например, если V=a, b, c, то V*=ε, a, b, c, aa, ab, ac, ba, abc, …, где ε – пустая цепочка, не содержащая символов. Очевидно, что хотя V конечно, V* – бесконечное счётное множество. Язык – это просто некоторое подмножество V*. Всего языков над словарем V бесконечное число; множество языков имеет мощность континуум.

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

1. V1={a, b, c}; L1={abc, cc}.

2. V2={a, b, c}; L2=∅.

3. V3={a, b, c}; L3=V*.

4. V4={a, b, c}; L4={an bcn |n≥ 0}.

5. V5={a, b, c}; L5={an bcm |n, m≥ 0}.

6. V6={a, b, c}; L6={α ∈ V* |в α количества вхождений a, b, c равны}.

7. V7={0, 1}; L7=множество чётных двоичных чисел.

8. V8={+, -, 0, …, 9}; L8=множество целых констант.

9. V9={a}; L9={α ∈ V* | длина α равна 2k, где k=0, 1, 2, …}.

10. V10={a}; L10={α ∈ V* | длина α равна 2k, где k=0, 1, 2, …}.

Определение 11. Любой конечный механизм задания языка называется грамматикой.

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

Роль распознающей грамматики может выполнить конечный автомат без выхода. Свяжем с некоторыми состояниями автомата метку «Да», а с остальными – метку «Нет». Тогда множество входных цепочек автомата разобьётся на два класса: одни – приводящие автомат в одно из состояний, помеченных «Да», все другие – приводящие автомат в одно из состояний, помеченных «Нет».

Определение 12. Конечным автоматом-распознавателем называется пятёрка объектов A=S, X, s0, δ, F, где:

S – конечное непустое множество состояний;

X – конечное непустое множество входных сигналов;

s0∈ S – начальное состояние;

δ: S× X⟶ S – функция переходов;

F⊆ S – множество заключительных (финальных) состояний.

Определим обобщённую функцию переходов автомата δ *∶ S× X*⟶ S точно так же, как в определении 3.

Определение 13. Конечный автомат-распознаватель A=S, X, s0, δ, F допускает входную цепочку α ∈ X*, если α переводит его из начального в одно из заключительных состояний, то есть если δ *s0, α ∈ F. Множество всех цепочек, допускаемых автоматом A, образует язык, допускаемый A.

Определение 14. Язык, для которого существует распознающий его конечный автомат, называется автоматным языком.

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

1. Автомат-распознаватель для языка L1 представлен на рис. 7.

Рис. 7. Автомат-распознаватель языка L1.

Входные цепочки abc и cc (и только они) переводят автомат из начального состояния в одно из заключительных состояний s3 или s5. Чтобы не загромождать граф, примем следующее соглашение. Если на графе не указан переход под воздействием некоторого входного сигнала a, то это означает, что существует незаключительное состояние, в которое автомат переходит по a, причём после этого под воздействием всех входных сигналов автомат не выходит из этого незаключительного состояния.

Рис. 8. Упрощённый граф автомата-распознавателя языка L1.

Очевидно, что любой конечный язык может быть задан конечным автоматом и поэтому все конечные языки – автоматные.

2. Любой автомат с пустым множеством заключительных состояний допускает L2.

3. Автомат с единственным состоянием, которое является заключительным, имеющий три перехода (помеченные символами a, b, c) из этого состояния в него же, допускает L3.

4. Язык L4 не является автоматным. Предположим противное: существует автомат A, который распознает L4. Пусть число состояний автомата A равно k. Рассмотрим цепочку akbck. Под воздействием первой части цепочки – k последовательных символов a – автомат обязательно вернётся в какое-либо из состояний, в котором он уже находился. Пусть это будет состоянием sn, и длина цепочки aaa…a, под воздействием которой автомат переходит из sn в sn, равна t (t> 0). Тогда цепочка ak-tbck тоже будет переводить автомат из начального состояния в заключительное состояние. Но ak-tbck∉ L4. Получили противоречие. Значит, автомата, распознающего L4, не существует.

Более общий критерий, позволяющий сделать заключение, является ли автоматным произвольный язык, даёт так называемая лемма о накачке.

5. В отличие от языка L4, язык L5 – автоматный. Автомат с двумя состояниями распознает L5 (рис. 9). Простота этого распознавателя объясняется тем, что он не должен отслеживать количества символов a и c во входных цепочках.

Рис. 9. Автомат, распознающий L5.

6. Язык L6 – не автоматный язык.

7. Автомат, распознающий L7, показан на рис. 10.

Рис. 10. Автомат, распознающий L7.

8. Автомат с тремя состояниями распознает L8 (рис. 11, вместо цифр на переходах поставлена буква «ц», обозначающая любую цифру).

Рис. 11. Автомат, распознающий L8.

9. Автомат, распознающий L9, показан на рис. 12.

Рис. 12. Автомат, распознающий L9.

10. Язык L10 – не автоматный язык.

Вопросы и упражнения.

Описать автоматы-распознаватели для языков над словарём {0, 1}:

1. Множество цепочек, оканчивающихся на 00;

2. Множество цепочек, содержащих три нуля подряд;

3. Множество цепочек, у которых на третьей позиции справа стоит 1.