Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Итерация А-языка есть А-язык. Действительно, если G есть А-грамматика с аксиомой A0, то добавление к ней всевозможных правил вида А~*аА0, где A-* а — правило G, дает А-грамматику, порождающую L(G)*. Легко видеть также, что обращение А-языка есть А-язык.
10.4.4. Теорема Клини
Класс А-языков совпадает с наименьшим классом языков, содержащим все конечные языки и замкнутым относительно операций объединения, умножения и итерации.
Доказательство. В одну сторону теорема следует из результатов п. 10.4.1—10.4.3, поскольку все конечные языки являются А-языками. Докажем обратное утверждение, т. е. покажем, что всякий А-язык может быть получен из конечных языков с помощью трех перечисленных операций. Для языка, порождаемого А-грамматикой, граф которой не содержит ни одной дуги, это утверждение очевидно. Пусть оно доказано для А-грамматик, графы которых содержат не более k дуг, и пусть G есть А-грамматика с k дугами в графе. Выбросим из этого графа некоторую дугу, ведущую из начальной вершины A0 в вершину В и помеченную символом а. Грамматику с таким графом обозначим G'. Грамматики, полученные из G': (1) переносом начальной вершины в В; (2) объявлением A0 единственной заключительной вершиной; (3) совместным выполнением предыдущих двух преобразований, — обозначим через Gi, G2 и G3 соответственно. Нетрудно видеть, что
L (G) = L (Gf) U L (G2) (aL (G3) )* aL (G1).
10.4.5. Разрешимые алгоритмические проблемы
Применительно к конечным автоматам могут быть сформулированы многие из тех проблем, которые возникали для машин Тьюринга и автоматов с магазинной памятью. Здесь эти проблемы оказываются, как правило, разрешимыми. А именно, существуют алгоритмы, позволяющие получить ответ «да» или «нет» на следующие вопросы: 170
Часть II. Некоторые замечательные классы языков
— допускает ли данный конечный автомат пустой язык;
— допускает ли данный автомат бесконечный язык;
— являются ли два данных конечных автомата эквивалентными.
10.4.6. Представление автоматных языков по Клини
Теорема Клини позволяет дать следующее простое рекурсивное определение А-языков.
Пусть имеется словарь V. Прежде всего мы определим представляющие выражения для цепочек из V*:
1) цепочка из V* есть представляющее выражение;
2) если X1 и X2— представляющие выражения, то XiX2 — тоже представляющее выражение,
3) если Xi (1 — представляющие выражения, то (Xir ..., Xim)', где ik = {1, - .., «}»— тоже представляющие выражения;
4) если Хь ..., Xn — представляющие выражения, то XiU ... ... U Xn — тоже представляющее выражение;
5) других представляющих выражений нет.
Эти выражения представляют множества цепочек из V* (языки в V) следующим образом:
1) цепочка из V* представляет самое себя (точнее, соответствующий «одноцепочечный язык»);
2) если Xi представляет множество Si, a X2 — множество S2, то XiX2 представляет S1S2, т. е. множество всех цепочек cpicp2, таких, что фі є 21 и ф2 є 2г;
3)—4) если Xi (1-Ci-^n) представляют множества цепочек 2і (1 -sCt-^Cra), то (Xji, ..., Xim)* представляет множество (Si U
... и S1J*, a X1 U ... U Xn — множество Si U ... USn.
В силу теоремы Клини всякий А-язык может быть задан некоторым представляющим выражением.
Примеры.
ab представляет язык, содержащий ровно одну цепочку ab;
(а)* представляет язык {ага|«^0}; (а)*(Ьу представляет язык {apbq\p, q^O}; (a, by представляет свободную полугруппу с образующими {а, Ь}\
(a)* U (0)" представляет язык {ар\ p>0}U{&? 1<7>0}.
Представляющим выражениям можно ставить в соответствие графы; например: Гл. X. Автоматные языки и конечные автоматы
171
Представляющее выражение
Соответствующий граф
О г)
ab
a b
О-,0
3)
(af
Qt
(а)'(Ь)"
Ql
X/
V a^vW.O5Tafi,a7f аЛ
6) (a'Jufb)'
Для'четвертого представляющего выражения обе вершины заключительные, а для шестого выражения все три вершины заключительные. Эти графы совпадают, очевидно, с графами соответствующих А-грамматик.
§ 10.5. А-ЯЗЫКИ И КС-ЯЗЫКИ
10.5.1. Самовставление
Особенность А-языков по сравнению с КС-языками заключается в том, что всякий А-язык может быть порожден грамматикой, в которой нет ни одного вспомогательного символа с самовставлением, тогда как существуют КС-языки, которые не порождаются никакими КС-грамматиками без самовставления.
Рассмотрим язык L = {anbn | п > 0}, порождаемый КС-грамматикой:
S-*aSb S->ab 172
Часть II. Некоторые замечательные классы языков
Докажем, что он не может быть порожден никакой А-грамма-тикой. Допустим, что А-грамматика, порождающая язык L, существует. Поскольку L бесконечен, в этой грамматике должны быть возможными выводы вида Ai=^xAu где х имеет вид аР; следовательно, в этой грамматике должны быть возможными и выводы вида
Al^yAh у = aqbr I q, О, Al^zAh z = bm.
Тогда данная грамматика будет порождать некоторые цепочки вида aPbi, где P^qi).
А-язык может быть порожден и грамматикой с самовставлением. Однако на вопрос, можно ли по данной КС-грамматике определить, порождает она А-язык или нет, приходится ответить отрицательно; это следует из нераспознаваемости автоматности дополнения к КС-языку (см. п. 8.1.2) 2).
