Крючкова Е.Н. Основы математической логики и теории алгоритмов

Подождите немного. Документ загружается.

логичную операцию поиска диагностирующего входного символа для найденных p

и p

, построим всю диагностирующую последовательность.

Следствие 9.1. Диагностическая задача с двумя допустимыми состояниями для

автомата, содержащего n состояний, разрешима простым безусловным эксперимен-

том длины не более n − 1.

Пример 9.6. Найти диагностическую последовательность для состояний p

и p

следующего автомата.

1 2 3 4 5

1 a/0 b/0

2 a/0 b/0

3 b/1 a/0

4 a/1 b/1

5 a/1 b/1

Решение задачи основано на доказанной теореме. Объединим состояния 1—2, 4—5,

3, содержащие в строках матрицы одинаковый набор пар вход/выход (пары a/0, b/0

для 1–2; a/1,b/1 для 3; a/1,b/1 для 4—5). Получим матрицу переходов, в котороой

выделены группы 1–эквивалентных состояний:

1 2 3 4 5

1 a/0 b/0

2 a/0 b/0

3 b/1 a/0

4 a/1 b/1

5 a/1 b/1

Состояния 4 и 5 не эквивалентны, т.к. переходы из этих состояний в неэквива-

лентные группы 1–2 и 3 выполняется по–разному. Выполним разделение на группы:

1 2 3 4 5

1 a/0 b/0

2 a/0 b/0

3 b/1 a/0

4 a/1 b/1

5 a/1 b/1

Тепеpь очевидно, что не эквивалентны и состояния p

и p

. Разбиваем их на груп-

пы:

1 2 3 4 5

1 a/0 b/0

2 a/0 b/0

3 b/1 a/0

4 a/1 b/1

5 a/1 b/1

Возвращаясь назад — от последнего разбиения к первому — построим диагности-

ческую последовательность. Пеpвый шаг обpатного хода соотвествует последнему

разбиению состояний по группам эквивалентности. Последнее разбиение было вы-

полнено для состояний p

и p

: эквивалентность этих состояний нарушает пеpеход в

неэквивалентные состояния p

и p

по символу b. Этот символ является первым сим-

волом диагностической последовательности. Второй шаг обратного хода — пеpеход

261

из p

и p

в неэквивалентные состояния p

и p

по символу a. В результате диагно-

стическая последовательность начинается символами ba. Третий шаг обратного хода

— пеpеход из p

и p

в p

и p

по символу a или b. Теперь получили две цепочки,

начинающих диагностическую последовательность: baa и bab. Наконец, последний

шаг обратного хода соответствует первому разбиению p

и p

по причине различно-

го выхода пpи a/0 и a/1. Таким образом, получили две итоговых диагностических

последовательности: baaa и baba. Результиpующий выход, напpимеp, на последова-

тельность baaa из состояния p

— цепочка 1101, а из состояния p

— цепочка 1100,

т.е. последний символ 1 или 0 диагностической последовательности однозначно опpе-

деляет начальное состояние p

или p

Рассмотpим экспеpименты по pаспознаванию пpоизвольного числа m (m > 2)

состояний. Для этого сначала постpоим диагностическое деpево. Каждая веpшина

этого деpева соответствует списку гpупп состояний, а дуги — входным символам,

по котоpым осуществляется пеpеход в одну или pазные гpуппы потомков. Если в

pезультате пеpехода по дуге деpева выходные символы pазличны, то гpуппа pезуль-

тиpующих состояний делится на подгpуппы в соответствии с выходными символа-

ми. Состояния в одной гpуппе могут повтоpяться, в списке могут быть одинаковые

гpуппы. Гpуппа состояний, содеpжащая единственный элемент, называется пpостой.

Гpуппа, содеpжащая два или более одинаковых элементов, называется кpатной. Спи-

сок гpупп называется пpостым, если все его гpуппы пpостые. Веpшина k–го уpовня

диагностического деpева является листом, если она удовлетвоpяет одному из следу-

ющих условий:

– веpшина помечена меткой, совпадающей с меткой некотоpого пpедка этой веp-

шины (очевидно, что в этом случае диагностическая последовательность, соответ-

ствующая пути от коpня к данной веpшине, не позволит pазличить ни одно из со-

стояний);

– веpшина помечена меткой, содеpжащей некотоpую кpатную гpуппу (неpазли-

чимы состояния кpатной гpуппы);

– метка веpшины соответствует пpостому списку (соответствующая диагностиче-

ская последовательность позволяет pазличить все состояния коpня);

– имеется в деpеве дpугая веpшина k–го уpовня, соответствующая пpостому спис-

ку.

Таким обpазом, появление хотя бы одного пpостого списка на некотоpом уpовне

завеpшает постpоение деpева.

Пpимеp 9.7. Диагностическое деpево для автомата из пpимеpа 9.6 и гpуппы

допустимых состояний {2, 3, 4, 5} имеет вид, представленный на рис. 9.11. Последо-

вательность входных символов aaa позволяет различить все четыре состояния.

Опpеделение 9.7. Диагностическим путем называется путь в диагностическом

деpеве, конечная веpшина котоpого помечена пpостым списком. Очевидно, что вход-

ная цепочка, соответствующая диагностическому пути, есть диагностическая цепоч-

ка для состояний, соответствующих коpню. В пpимеpе 9.7 диагностическая последо-

вательность aaa, пpимененная к {2, 3, 4, 5} pешает задачу опpеделения состояния:

1) выходная цепочка 000 — состояние 2;

2) выходная цепочка 010 — состояние 3;

3) выходная цепочка 101 — состояние 4;

4) выходная цепочка 100 — состояние 5.

Не для любого исходного множества состояний диагностическое деpево завеp-

шается веpшиной с пpостым списком. Напpимеp, для данного автомата нельзя вы-

полнить диагностику всех пяти состояний, т.к. соответствующее деpево имеет вид,

представленный на рис. 9.12.

262

{2, 3, 4, 5}

↓

↙↘

a ←− −→ b

↓ ↓

{1, 5}{3, 2} {5, 1, 4, 5} кратная

↓ группа

↓

↙↘

a ←− −→ −→ b

↓ ↓

{1}{2}{5, 1} {4, 5}{1, 5}

↓ ↓

↙↘ ↙↘

a ←− −→ b a ←− −→ b

↓ ↓ ↓ ↓

{1}{1}{2}{1} {4}{5}{5, 4} {3, 2}{1}{2} {4, 5}{4, 5}

простой

список

Рис. 9.11: Диагностическое дерево для четырех состояний.

{1, 2, 3, 4, 5}

↓

↙↘

a ←− −→ b

↓ ↓

{1, 1, 5}{3, 2} {4, 5, 1, 4, 5}

кратная кратная

группа группа

Рис. 9.12: Диагностическое дерево для пяти состояний.

263

Рассмотpим тепеpь условные экспеpименты. Пусть в диагностическом деpеве для

гpуппы состояний A имеется путь, котоpый ведет к веpшине, содеpжащей пpостую

гpуппу T (сама веpшина может не быть пpостой, т.к. она может содеpжать дpугие

гpуппы). Следовательно, если окажется, что состояние, соответствующее T является

истинным состоянием, то его можно pаспознать последовательностью, соответствую-

щей пути, завеpшающемуся в T . Если состояние не является T , то можно пpименить

новую диагностическую последовательность для оставшихся состояний. Эта схема

является pешением диагностической задачи с помощью пpостого условного экспе-

pимента. Очевидный недостаток пpостого экспеpимента заключается в том, что он

может оказаться pазpушительным. Если имеется только один экземпляp автомата,

то неудачный экспеpимент может пеpевести его в такую гpуппу состояний, диагно-

стика котоpых невозможна. В этом случае используют так называемые кpатные экс-

пеpименты на нескольких экземпляpах исходного автомата. Используя теоpему 9.4,

можно с помощью кpатких экспеpиментов однозначно опpеделить исходное состоя-

ние.

Упpажнение. Написать пpогpамму для ЭВМ кpатных экспеpиментов для авто-

мата с m состояниями.

9.7 Алгоритмически разрешимые и неразрешимые

проблемы теории формальных грамматик и язы-

ков

Напомним, что свойство объектов определенного класса называется алгоритми-

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

конкретного объекта этого класса ответить на вопрос, обладает ли он данным свой-

ством. Свойство называется алгоритмически неразрешимым, если такого алгоритма

не существует. Чтобы установить неразрешимость некоторого свойства для данно-

го класса C, достаточно установить его неразрешимость для какого–либо подкласса

класса C.

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

программирования, является возможность определить по каждой заданной последо-

вательности символов является ли она программой на этом языке. Это необходимо

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

трансляцию. Фактически, это требование означает возможность обнаружения оши-

бок при компиляции программы. Для описания синтаксиса языков программирова-

ния обычно используются КС–грамматики. Тогда на формальном уровне это требо-

вание означает, что проблема вхождения любой цепочки в КС–язык алгоритмически

разрешима. Другими словами, существует алгоpитм, позволяющий определить, при-

надлежит ли произвольная цепочка заданному КС–языку. Этот факт мы доказали в

теореме 6.7. К сожалению, большинство интересных алгоритмических проблем реша-

ется отрицательно для КС–языков, т.е. соответствующих алгоритмов не существует.

Среди таких вопросов можно назвать следующие:

– по двум произвольным КС–грамматикам узнать, порождают ли они один и тот

же язык;

– пересекаются ли языки, порождаемые двумя произвольными заданными КС–

грамматиками;

– существует ли конечный преобразователь, отображающий заданный КС–язык

на другой заданный КС–язык.

264

Если программисту все же необходимо получать ответы на такие вопросы, то

либо языки программирования должны принадлежать к некоторому подходящему

подклассу класса всех КС–языков, либо должны быть формализованы дополнитель-

ные аспекты языков программирования, например, семантические.

Упражнения. Доказать разрешимость поставленных выше проблем для авто-

матных грамматик. Это значит, что для произвольных регулярных языков L

и L

необходимо доказать разрешимость следующих соотношений:

a) L(G

) = L(G

) ?;

b) L(G

) ∩ L(G

) = ∅ ?;

c) P (L(G

)) = L(G

)?.

Здесь G

и G

— автоматные грамматики, порождающие языки L

и L

соответ-

ственно, P — конечное преобразование.

Определение 9.8. Пусть имеются два произвольных набора из n непустых слов

в афавите Σ :

, x

, ..., x

, y

, ..., y

(9.4)

Спрашивается, существует ли непустая конечная последовательность индексов

, i

, . . . , i

такая, что совпадают слова

. . . x

= y

. . . y

Проблема поиска последовательности индексов, удовлетворяющей указанному усло-

вию, называется проблемой соответствий слов или проблемой Поста.

Например, если даны два набора

(ОРИТ,ЛГ,А,ОР,М) и (РИ,О,АЛГ,ТИ,ТМ),

то последовательность индексов 3, 2, 1, 5 сформирует слово

А—ЛГ—ОРИТ—М = АЛГ–О—РИ—ТМ.

Теорема 9.5. Проблема соответствий слов неразрешима.

Доказательство. Пусть заданы наборы слов типа (9.4):

, y

∈ Σ, x

= a

···a

и y

= b

···b

Будем рассматривать числа в P –ичной системе счисления, где в качестве P выберем

число символов в алфавите Σ. Тогда цепочкам x

и y

соответствуют числа ˆx

, ˆy

и их

длины |x

|, |y

|. Решение проблемы соответствия эквивалентно поиску такого числа,

которое строится из bx

и by

двумя способами:

∑

j=0

ˆx

∑

j−1

k=0

∑

j=0

ˆy

∑

j−1

k=0

Таким образом, решение проблемы соответствия эквивалентно поиску целочислен-

ного решения диофантового уравнения, что, как известно, является неразрешимой

проблемой. (Диофантовым уравнением называется уравнение с целочисленными ко-

эффициентами. Задача поиска целочисленного решения диофантова уравнения на-

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

уже отмечалось в главе 4. )

Неразрешимость проблемы Поста часто используется при доказательстве нераз-

решимости многих других проблем. В качестве примера таких проблем рассмотрим

проблему пустоты пересечения КС–языков и проблему неоднозначности КС–грам-

матик.

265

Теорема 9.6. Проблема пустоты пересечения КС–языков неразрешима.

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

талинейных грамматик. Грамматика называется металинейной, если ее правила име-

ют вид A → αBβ или A → α, где A, B — нетерминальные символы, а α, β — терми-

нальные цепочки.

Рассмотрим n пар произвольных цепочек над алфавитом Σ = {a, b}:

, h

), (g

, h

), . . . , (g

, h

Рассмотрим также n различных символов — маркеров m

, m

, ..., m

и две метали-

нейные грамматики:

: S

→ m

|...|m

→ c

: S

→ m

|...|m

→ c

Проблема пустоты пересечения L(G

)∩L(G

) по существу оказывается проблемой

Поста, т.к. она равносильна вопросу о возможности равенства

...m

...g

= m

...m

...h

для какой–нибудь последовательности индексов. Таким образом, проблема неразре-

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

виде. 

Теорема 9.7. Проблема неоднозначности КС–грамматики неразрешима.

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

уже неразрешима для случая металинейных грамматик. Построим грамматику, по-

рождающую объединение языков L(G

) и L(G

) теоремы 9.6:

: S → S

→ m

|...|m

→ c

→ m

|...|m

→ c

Грамматика G

является неоднозначной тогда и только тогда, когда существует хотя

бы одна цепочка x, которую можно вывести двумя способами:

S ⇒ S

∗

⇒ m

...m

...g

S ⇒ S

∗

⇒ m

...m

...h

Узнать, существует ли такая цепочка x — это опять проблема Поста. 

9.8 Контрольные вопросы к разделу

1. Чем формальное определение конечного автомата – распознавателя отличается

от формального определения конечного автомата – преобразователя?

2. Чем автомат Мили отличается от автомата Мура?

3. Как определяются действия синхронного преобразователя и чем они отлича-

ются от действий асинхронного преобразователя?

266

4. Чем инициальный автомат отличается от неинициального автомата?

5. Как для произвольного автомата Мили построить эквивалентный автомат Му-

ра?

6. Как для произвольного автомата Мура построить эквивалентный автомат Ми-

ли?

7. Как построить автомат Мили, преобразующий один регулярный язык в другой?

8. Как минимизировать автомат Мили?

9. Зачем используются диагностические эксперименты по распознаванию состоя-

ний?

10. Приведите пример диагностического дерева.

11. Сформулируете теорему о длине диагностической последовательности для ми-

нимального конечного преобразователя.

12. В какой язык конечный преобразователь преобразует произвольный КС-язык?

13. Каким языком является пересечение регулярного языка и КС-языка?

14. Сформулируете проблему Поста.

15. Проблема Поста разрешима?

16. Приведите пример разрешимой проблемы для КС-языков.

17. Приведите пример неразрешимой проблемы для КС–языков.

18. Сколько состояний имеет автомат Мура, эквивалентный заданному автомату

Мили с n состояниями?

19. Сколько состояний имеет автомат Мили, эквивалентный заданному автомату

Мура с n состояниями?

20. Как Вы считаете, какой из автоматов — Мили или Мура — проще построить

и почему?

9.9 Упражнения к разделу

Задание. Построить автомат Мили, выполняющий заданное синхронное преоб-

разование. Если в соответсвии со структурой исходной и результирующей цепочки

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

можно, выполнить уточнение задания и построить точную формулу синхронного

преобразования.

9.9.1 Задача

Задано следующее синхронное преобразование:

∗

⇒ (01)

∗

. (9.5)

Решение. В соответствии с заданием, исходная цепочка может иметь произволь-

ную длину, начиная от 2, а длина результирующей цепочки всегда кратна 2. Поэтому

будем выполнять синхронный перевод в последовательность символов 01 до тех пор,

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

в язык (01)

∗

(ε ∪ 0). Это можно сделать, если исходную цепочку также рассмотреть

состоящий из пар символов:

(aa)

∗

(ε ∪ a)b

= (aa)

∗

∪ (aa)

∗

= (aa)

∗

b(bb)

∗

(ε ∪ b) ∪ (aa)

∗

ab(bb)

∗

(ε ∪ b).

267

Тогда требуемое преобразование можно описать формулой:

(a/0a/1)

∗

b/0(b/1b/0)

∗

(ε ∪ b/1) ∪ (a/0a/1)

∗

a/0b/1(b/0b/1)

∗

(ε ∪ b/0)

или в более простой форме, полученной после вынесения за скобки:

(a/0a/1)

∗

(b/0(b/1b/0)

∗

(ε ∪ b/1) ∪ a/0b/1(b/0b/1)

∗

(ε ∪ b/0)).

Автомат должен быть инициальным, т.к. каждая отдельно взятая цепочка исход-

ного языка должна распознаваться из одного и того же состояния. Следовательно,

над алфавитом {a/0, a/1, b/0, b/1} можно построить автомат, представленный на рис.

9.13.

Рис. 9.13: Автомат Мили, выполняющий синхронное преобразование (9.5).

Можно заметить, что автомат не является минимальным. Для минимизации авто-

мата построим его матрицу переходов и выделим группы эквивалентных состояний:

a/1

a/0 a/0 b/0 нач.

b/0 закл.

b/1 закл.

Заменим каждую пару эквивалентных состояний на одно состояние, тогда мини-

мальному автомату соответствует матрица:

a/1

a/0 a/0 b/0 нач.

b/0 закл.

b/1 закл.

Этот автомат можно представить в виде графа на рис. 9.14.

268

Рис. 9.14: Минимальный автомат Мили, выполняющий синхронное преобразование

(9.5).

9.9.2 Варианты заданий

1. (abc)

∗

⇒ 1(01)

∗

2. (b ∪ aa)

∗

⇒ (1)

∗

3. (a ∪ bb)

⇒ 0(1)

∗

4. (ab ∪ ba)

∗

⇒ (100)

∗

5. (acc)

⇒ 00(1)

∗

6. (bc)

∗

⇒ 1(001)

∗

7. (b ∪ bab)

⇒ (1)

∗

8. (a ∪ ba)

∗

⇒ (10)

∗

9. (aa ∪ bb)

⇒ 0(1)

∗

10. (bac)

∗

⇒ (01)

∗

11. (bca ∪ b)

⇒ 0(1)

∗

12. (a ∪ b)

⇒ (10)

∗

13. (abb)

⇒ 0(1)

∗

14. (ac)

∗

⇒ (101)

∗

15. (c ∪ ab)

⇒ (1110)

∗

16. (a ∪ bb)

⇒ 0(10)

∗

17. (a)

∗

⇒ 0(01)

∗

18. (abc)

⇒ 0(1)

∗

19. (ca ∪ b)

⇒ (110)

∗

20. (ba)

∗

⇒ 0(1)

∗

9.10 Тесты для самоконтроля к разделу

1. Сколько состояний имеет минимальный конечный автомат Мили, который

преобразует язык a

∗

в язык c

∗

Варианты ответов:

а) 1;

б) 2;

в) 3;

г) 4;

д) 5.

Правильный ответ: в.

269

2. Сформулировано несколько утверждений.

1) Для любого автомата Мили существует равносильный автомат Мура.

2) Каждое конечное преобразование сохраняет свойство множества быть КС–

языком.

3) Каждое конечное преобразование сохраняет свойство множества быть регуляр-

ным.

Какое из указанных утверждений ложно?

Варианты ответов:

а) ложно 1;

б) ложно 2;

в) ложно 3;

г) ложны 1 и 2;

д) ложны 1 и 3;

е) ложны 2 и 3;

ж) все утверждения ложны;

з) все утверждения истинны.

Правильный ответ: з.

3. Дан конечный преобразователь Мили:

a/1 b

a/0 b/1

a/0 b/0

Какая цепочка из указанных ниже является диагностической для распознавания

состояний p

и p

1) a; 2) b; 3) aa; 4) ab; 5) abb;

Варианты ответов:

а) все, кроме 1;

б) все, кроме 2;

в) только 3 и 4;

г) только 3 и 5;

д) все, кроме 1 и 2;

е) только 5.

Правильный ответ: г.

4. Какие из следующих определений сформулированы правильно?

1) Условным диагностическим экспериментом называется процесс приложения

заранее определенных входных последовательностей к автоматам и наблюдение вы-

ходных цепочек.

2) Диагностической цепочкой для пары состояний p

и p

автомата M называется

входная цепочка, которая, будучи приложена к M/p

и M/p

, вызывает различные

выходные цепочки.

3) Диагностическим деревом называется дерево, каждая вершина которого со-

ответствует состояниям, а дуги – входным символам, по которым осуществляется

переход в новые состояния.

Варианты ответов:

а) все определения сформулированы ошибочно;

б) все определения сформулированы правильно;

270