Критерии конечно-автоматности языков

Конечно-автоматные языки можно охарактеризовать в терминах взаимозамещаемости слов. Введём для этого необходимые понятия.

Пусть даны произвольный язык A в алфавите X, а также пара слов p, r в этом же алфавите X (допускаются и пустые слова).

Слова p, r назовём взаимозамещаемыми в языке A (обозначение p » r (A)), если выполнено условие: каковы бы ни были слова (возможно, пустые) x, y, слово xpy принадлежит языку A тогда и только тогда, когда слово xry также принадлежит языку A.

Слова p, r назовём левовзаимозамещаемыми (правовзаимозамещаемыми) в языке A (обозначения соответственно p »_л r (A)), p »_п r (A)), если выполнено условие: каково бы ни было слово x, слово px (соответственно xp) принадлежит языку A тогда и только тогда, когда слово rx (соответственно xr) также принадлежит языку A.

Из этих определений непосредственно вытекают следующие утверждения:

1. Отношение взаимозамещаемости (правой, левой) для слов является отношением эквивалентности, и, следовательно, оно разбивает всеобщий язык в X (т.е. множество X* ^ = X* È{Ù} всех, включая пустое слово Ù, слов в X) на классы взаимозамещаемости (соответственно правой, левой взаимозамещаемости). Его ранг (т.е. мощность множества всех классов эквивалентности) может оказаться бесконечным. Например, пусть язык B состоит из всех слов, длины которых являются точными квадратами. Тогда, как нетрудно видеть[1], взаимозамещаемы лишь такие слова, которые имеют одинаковую длину. Поскольку взаимозамещаемость слов влечёт за собой их правую (левую) взаимозамещаемость, то разбиение на классы взаимозамещаемости является более мелким, чем разбиение на классы правой (левой) взаимозамещаемости. Иными словами, всякий класс правой (левой) взаимозамещаемости либо является классом взаимозамещаемости, либо разбивается на несколько таких классов.
2. Пусть p »_л r; тогда для любых x вернотакже px »_л rx. В частности, прибавление справа к левовзаимозамещаемым словам одной и той же буквы превращает их опять-таки в левовзаимозамещаемые слова. Поэтому можно определить операцию умножения класса левой взаимозамещаемости A_i на букву (любую) a. Именно, произведение A_i a — это тот класс левой взаимозамещаемости, в который попадают все слова вида p a, где p Î A_i.
3. Язык A являетсяобъединением некоторых классов взаимозамещаемости (правой взаимозамещаемости, левой взаимозамещаемости), порождённых им, или совпадает с одним из этих классов.

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

ТЕОРЕМА 2. (I) Если автомат M представляет язык A с левой взаимозамещаемостью ранга m, то число состояний в M не меньше m. (II) Для всякого языка A с левой взаимозамещаемостью ранга m существует представляющий его автомат с m состояниями.

Один из критериев конечно-автоматности языков задаётся этой теоремой как её

СЛЕДСТВИЕ. Для того, чтобы язык A был конечно-автоматным, необходимо и достаточно, чтобы порождаемая им система классов левой взаимозамещаемости была конечной.

Теорема 2 не распространяется на правуювзаимозамещаемость. Однако нужно иметь в виду следующее

ЗАМЕЧАНИЕ 2. Отражением A ^-1 языка A называется язык, состоящий из слов языка A, выписанных в обратном порядке вхождений букв. Например, если a (1) a (2) … a (n) Î A, то a (n) … a (2) a (1) Î A^-1.

Пусть ранг правойвзаимозамещаемости для языка A равен m. Тогда таковым же будет ранг левой взаимозамещаемости отраженного языка A ^-1. Если при этом m конечно, то A ^-1 — конечно-автоматный язык. Можно показать, что при этом также и A — конечно-автоматный язык, однако число состояний представляющего автомата для A, вообще говоря, больше m.

КОНЕЦ

Лекция 14

Теорема 2 и её следствия позволяют просто указывать эффективные, но не конечно-автоматные языки.

Рассмотрим, например, язык A, состоящий из всех слов вида 0ⁿ10ⁿ, где 0ⁿ обозначает слово их n нулей (n = 1, 2, …). Допустим, что A — конечно-автоматный язык; тогда среди слов 0, 00, 000, … найдётся пара левовзаимозамещаемых (ведь согласно следствию из теоремы 2 число классов левой взаимозамещаемости должно быть конечным). Пусть 0^k »_л 0^s (A). В таком случае в A наряду со словом 0^k10^k должно было бы содержаться и слово 0^s10^k (0^k = p, 0^s = r, x = 10^k, px = 0^k10^k, rx = 0 ^s10^k), которое, по условию, не принадлежит A. Противоречие. Следовательно, язык A непредставим в конечном автомате.

Это рассуждение на самом деле устанавливает следующий общий факт, который можно сформулировать в терминах отделимости языков.

Будем говорить, что язык B отделяет язык A₁ от (непересекающегося с ним) языка A_2, если B Ê A ₁ и B Ç A ₂ = Æ.

Далее, язык A₁ конечно-автоматно отделим от языка A_2, если существует конечно-автоматный язык B, отделяющий A₁ от A₂ (в таком случае, как легко видеть, и A₂ конечно отделим от A₁ языком Ø B, а поэтому можно рассматривать симметричное отношение конечно- автоматной отделимости языков).

В нашем примере мы можем теперь заметить, что язык {0ⁿ10ⁿ} не отделим конечно-автоматно от языка {0^k10 ^s} (k ¹ s).

Приведём (без доказательств) ещё два результата, каждый из которых полезно рассматривать как некоторый (условный или безусловный) критерий конечно-автоматности языков:

Первый результат.

Следуя Ю.Т. Медведеву, для фиксированного алфавита X = { a ₁, a ₂, …, a _m} назовём элементарными следующие языки:

A₁ — язык, состоящий из однобуквенных слов, A ₂ — язык, состоящий из двухбуквенных слов, B _i — язык, состоящий из всех слов, оканчивающихся буквой a _i (i £ m);

C_i — язык, состоящий из всех слов длины, не меньшей чем 2, в которых предпоследней буквой является a _i (i £ m).

Медведев доказал:

Класс языков (в алфавите X), представимых в конечных автоматах, есть наименьший класс языков, содержащий все элементарные языки и замкнутый относительно объединения È, пересечения Ç, дополнения Ø и двух следующих операций, каждая из которых преобразует язык A в язык A¢:

1) A¢ состоит в точности из тех слов, которые имеют начальный кусок, принадлежащий A.

2) Пусть a_i, a_j — некоторые буквы алфавита X = { a ₁, a ₂, …, a _m}. A ¢ получается из A, если заменить в каждом слове из A все вхождения буквы a_i вхождениями буквы a_j.

Второй результат.

Для каждого n в алфавите {0, 1} существует язык, представимый в автомате с n состояниями и такой, что соответствующий отражённый язык не представим ни в каком автомате с числом состояний, меньшим чем 2 ⁿ. (Ср. с замечанием 2.)

Третий.

Пусть A — конечно-автоматный язык, который не имеет слов нечётной длины. Тогда левые (правые) половины слов языка A образуют конечно-автоматный язык.

Четвёртый.

Пусть A — конечно-автоматный язык, который содержит только слова, длины которых кратны трём. Тогда язык, состоящий из «средних третей» слов языка A, является конечно-автоматным. Однако язык, который состоит из слов, полученных в результате удаления «средних третей» из слов языка A, может не быть конечно автоматным. (Убедиться в этом можно на примере конечно автоматного языка A, состоящего из всех двоичных слов длины, кратной трём, которые не содержат подряд двух единиц.)

КОНЕЦ

Лекция 15