Главная Промышленная автоматика.

гл. Q. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ

2.3.4. Разрешимые проблемы связанные с регулярными множествами

Мы изложили несколько способов описания регулярных множеств, таких, как регулярные выражения и конечные автоматы. В связи с этими способами представления языков естественно возникают алгоритмические проблемы. Мы коснемся здесь трех проблем:

Проблема принадлежности: „Даны определенного типа описание языка и цепочка w\ принадлежит лн w этому языку?"

Проблема пустоты: ,Дано определенного типа описание языка; пуст ли этот язык?"

проблема эквивалентности: „Даны два описания одинакового типа; определяют ли они один и тот же язык?"

Мы рассмотрим следующие типы описаний регулярных множеств:

(1) регулярные выражения,

(2) праволинейные грамматики,

(3) конечные автоматы.

Сначала дадим алгоритмы, решающие три упомянутые выше проблемы в том случае, когда языки описываются с помощью конечных автоматов.

Алгоритм 2.3. Решение проблемы принадлежности для конечных автоматов.

Вход. Конечный автомат М = (Q, 2, 6, q, F) и цепочка w G 2*. Выход. „ДА", если wL(M)\ „НЕТ", если wL{M), Метод. Пусть w = aa ... а. Найти последовательно состояния qbiq, а,), q., = {q,, я)- • Яn[Qn-, й- Если qF, сказать ,ДА"; если qF, сказать „НЕТ". П

Корректность алгоритма 2.3 слишком очевидна, чтобы ее обсуждать. Однако стоит обсудить временную и емкостную сложности этого алгоритма. Естественными мерами сложности в дан-Ном случае служат число шагов и число ячеек памяти, требуемых вычислительной машине с произвольным доступом к памяти, у которой каждая ячейка памяти может хранить целое число произвольной величины. (Фактически в реальных вычислительных машинах величина чисел ограничена, но эта граница так велика, что, несомненно, для тех конечных автоматов, которые имеет смысл рассматривать, она никогда не будет достигнута. Таким образом, предположение о неограниченности чисел является здесь разумным математическим упрощением.)

Легко видеть, что время работы алгоритма линейно зависит от длины цепочки. Однако ие совсем ясно, влияет ли на время работы „объем" автоматам. Мы должны предположить, что фак-

тически описание автомата М представляет собой цепочку символов, взятых из некоторого конечного алфавита. Поэтому можно предположить, что именами состояний являются q, . . ., qi, .. . , где индексы записаны в виде двоичных чисел. Аналогично обстоит дело с именами входных символов а, а, ... . Если предполагается машина обычного типа, то для хранения функции б можно построить двумерный массив, такой, что в ячейке (t, /) находится 6(9-, йу). Итак, общее время работы алгоритма будет состоять из времени, необходимого для построения этой таблицы, которое пропорционально длине описания М, и времени выполнения самого алгоритма, которое пропорционально г:.

Требуемый объем памяти - это главным образом число ячеек, необходимых для хранения таблицы, оно пропорционально длине описания М.

Теперь дадим алгоритмы решения проблем пустоты и эквивалентности, когда описаниями языков служат конечные автоматы.

Алгоритм 2.4. Решение проблемы пустоты для конечных автоматов.

Вход. Конечный автомат M={Q, 2, 6, q, F). Выход. „ДА", если L(M)0, „НЕТ" в противном случае. Метод. Вычислить множество состояний, достижимых из q,. Если это множество содержит какое-нибудь заключительное состояние, то сказать ,ДА", в противном случае сказать „НЕТ". □

Алгоритм 2.5. Решение проблемы эквивалентно-стидляконечныхавтоматов.

Вход. Два конечных автомата Mi-(Qi, Sj, б, q, F) и,

3=(2. 2. s.-a). таких, что Qf]Q=0.

Выход. ,ДА", если L (MJ (Ма), „НЕТ" в противном случае. Метод. Построить конечный автомат

M = {Q,[JQ,, 2,U2„ 6,ий,, qi, F,[jF,)

С помощью леммы 2.11 определить, различимы ли состояния q и 9-2- Если да, то сказать „НЕТ", в противном случае сказать ,ДА". □

Отметим, что для решения проблемы эквивалентности можно было бы воспользоваться алгоритмом 2.4, так как L(Mj) = L{M2) тогда и только тогда, когда

{L (М,) и L (М J) и {L (МО П L (М,)) = 0

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



или праволинейными грамматиками. Легко показать, что для этих способов представления языков все три проблемы тоже разрешимы. Регулярное выражение можно превратить в эквивалентный конечный автомат с помощью алгоритма, который извлекается из доказательств лемм 2.9 и 2.10. Затем к полученному автомату можно применить один из алгоритмов 2.3-2.5. Праволинейную грамматику можно превратить в эквивалентное регулярное выражение с помощью алгоритма 2.1 и алгоритма, который неявно содержится в доказательстве теоремы 2.2. Ясно, что эти алгоритмы слишком непрямые, чтобы их можно было использовать на практике. Прямые быстро работающие алгоритмы будут предметом нескольких упражнений. Сформулируем эти результаты в виде теоремы.

Теорема 2.10. Если множества определяются конечными автоматами, регулярными выражениями или праволинейными грамматиками, то проблемы принадлежности, пустоты и эквивалентности для регулярных множеств алгоритмически разрешимы. □

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

Пример 2.17. Можно устроить перечисление машин Тьюринга (см. упражнения к разд. 0.4) в виде списка Mj, М, .... Затем можно определить представление регулярных множеств с помощью натуральных чисел, а именно

(1) если Ml допускает регулярное множество, то пусть число i представляет это множество,

(2) если М допускает не регулярное множество, то пусть число i представляет множество {е}.

Каждое положительное целое число представляет, таким образом, некоторое регулярное множество, н каждое регулярное множество представляется хотя бы одним таким числом. Известно, что для использованного здесь представления машин Тьюринга проблема пустоты неразрешима (упр. 0.4.16). Допустим, что разрешима проблема: „Представляет ли число i пустое множество 0?" Легко видеть, что машина Mi допускает 0 тогда и только тогда, когда число / представляет 0. Следовательно, если регулярные множества определяются только что описанным способом, то проблема пустоты для них неразрешима. □

УПРАЖНЕНИЯ

2.3.1. Дан конечный автомат с п достижимыми состояниями. Каково наименьшее число состояний эквивалентного ему приведенного автомата?

2.3.2. Найдите конечный автомат с минимальным числом состояний для языка, определяемого автоматом М = ({А,В,С, В, Е, F}, {О, 1}, 6, Л, {Е, F}), где функция 6 задается табл. 2.4.

Таблица 2.4

Состояние А

Вход

2.3.3. Покажите, что для любого п существует такой конечный автомат с п состояниями, что ="~ Ф=~.

2.3.4. Докажите, что для автомата М, который строится алгоритмом 2.2, Z,(M)=L(M).

Определение. Отношение R, определенное на 2*, называется правоинеариантным, если xRy влечет xzRyz для всех х, у, z из S*.

2.3.5. Покажите, что L - регулярное множество тогдаитолько тогда, когда L можно представить в виде объединения некоторого числа классов эквивалентности правоинвариантного отношения эквивалентности R конечного индекса. Указание: Для доказательства необходимости определите отношение R, положив тогда и только тогда, когда (t/g, х) \-* {р, е), {q,, у) \-* (q, е) и p = q (т. е. цепочки хяу переводят конечный автомат, определяющий L, в одно и то же состояние). Покажите, что R - правоинвариантное отношение эквивалентности конечного индекса. Для доказательства достаточности постройте конечный автомат, определяющий L, беря в качестве его состояний классы эквивалентности отношения R.

Определение. Отношение Е назовем грубейшим правоинеариантным отношением эквивалентности для языка LS*, если хЕу тогда И только тогда, когда для всех ;г 6 2* цепочка xz принадлежит L в точности в тех случаях, когда yzL.

Следующее упражнение устанавливает, что каждое правоинвариантное отношение эквивалентности, определяющее язык L, содержится в Е.

2.3.6. Пусть L - объединение некоторых классов эквивалентности правоинвариантного отношения эквивалентности R, опре-



деленного на 2*. Пусть £ -грубейшее правоипвариантное отношение эквивалентности для языка L. Покажите, что ER.

*2.3.7. Покажите, что грубейшее нравоннвариантное отношение эквивалентности для языка L имеет конечный индекс тогда и только тогда, когда L - регулярное множество.

2.3.8. Пусть M = {Q, 2, б, q, F) - приведенный конечный автомат. Определим отношение Е на 2*, положив хЕу тогда и только тогда, когда (q, х)* (р, е), (q, у)* (q, е) и я = 7- Покажите, что - грубейшее правоинвариантное отношение эквивалентности для L{M),

Определение. Отношение эквивалентности R на S* называется отношением конгруэнтности, если R одновременно лево- и пра-Боинвариантно (т. е. если xRy, то wxzRwyz для всех w, х, у, z из 2*).

2.3.9. Покажите, что L - регулярное множество тогда и только тогда, когда L можно представить в виде объединения некоторых классов эквивалентности отношения конгруэнтности конечного индекса.

2.3.10. Покажите., что если и - приведенные конечные автоматы, для которых (Mi) £ (Мд), то их диаграммы равны.

*2.3.11. Покажите, что нижняя граница временной сложности алгоритма 2.2 равна гс (т. е. существует такой автомат М z п состояниями, что алгоритму 2.2 требуется произвести п, операций, чтобы найти приведенный автомат, эквивалентный М). Какова верхняя граница временной сложности алгоритма 2.2?

Можно найти алгоритм минимизации числа состояний конечного автомата, время работы которого всегда не превосходит nlogn, где п-число состояний минимизируемого автомата. Больше всего времени требует тот этап алгоритма 2.2, который на шаге 2 находит классы эквивалентности отношения методом леммы 2.И. Однако на шаге 2 можно использовать другой алгоритм, который позволяет сократить время работы алгоритма 2.2 до я log/г.

Этот новый алгоритм несколько иначе, чем в лемме 2.11, измельчает разбиения множества состояний. Вначале все состояния разбиты па заключительные и незаключительпые. Далее допустим, что некоторое разбиение состоит из классов л, л, ... ..., й-!- Для того чтобы сделать это разбиение более мелким, выберем класс я- и входной символ а. Каждый класс я, содержащий такое состояние q, что 6(9, а)п, расщепляется на два класса; JxJ-= {9 9 и 6 (9, а) 6 j} и я} = Ду -л. Таким обра-

зом, в отличие от метода леммы 2.11 здесь происходит расщепление класса, как только выясняется, что данный вход переводит некоторые состояния этого класса в такие, неэквивалентность которых установлена ранее.

Алгоритм 2.6. Нахождение классов неразличимых состояний конечного автомата.

Вход. Конечный автомат M = (Q, 2, Й, q, F). Выход. Классы эквивалентности отношения =. Метод.

(1) Найти ((?, а) - {я I б (я, u) - q} для всех q,Q и а 2. Положить п- = {q \ дп. и б" (q, а) Ф 0\.

(2) Положить 1/ и n = Q - F.

(3) Для всех а £2 определить множества индексов

( {!}, если / {а)-\

{2} в противном случае.

(4) Положить 3.

(5) Выбрать а2 и i£l{a). Если 1{а) = 0 для всех а 2, остановиться. Выход-мпожество классов л, я, ...,я,; .

(6) Удалить / из множества / (а).

(7) Для всех / <к, для которых cyntecTByeT q £ Яу и б (q, а) я,-, сделать шаги (а) - (г):

(а) Положить Я; {9 I б (9, а) л,- и qnjn Я/Яу -я;.

(б) Заменить я на nj и положить Яд = я/; построить новые Яу д и Яд для всех й2.

(в) Для всех а2 изменить I (а), положив

/(а) Ни{/}- если / / (а) и О < # Яу, , < # я,. „ { I (a){j {k} в противном случае.

(г) Положить k=k-\-\.

(8) Перейти к шагу 5. □

2.3.12. Примените алгоритм 2.6 к конечным автоматам из примера 2.15 и упр. 2.3.2.

2.3.13. Докажите, что алгоритм 2.6 правильно находит классы неразличимых состояний конечного автомата.

**2.3.14. Покажите, что алгоритм 2.6 можно реализовать за время п log п.

2.3.15. Покажите, что следующие множества не регулярны:

(а) {0"10"гг> 1},

(б) {ww\w£\0, \\*],

(в) L{G), где С определяется правилами S->aSbS\c,

(г) {й" I д> 1},





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [25] 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0019