- •4. Эквивалентные преобразования кс- и а-грамматик
- •4.1. Декомпозиция правил грамматики
- •4.2. Исключение тупиков
- •4.3. Обобщенные кс-грамматики и приведение их к удлиняющей
- •4.4. Устранение левой рекурсии и левая факторизация
- •5. Свойства автоматных и контекстно-свободных
- •5.1. Общий вид цепочек а-языков
- •5.2. Общий вид цепочек кс-языков
- •5.3. Операции над языками
- •5.3.1. Операции над кс-языками
- •5.3.2. Операции над а-языками
- •5.3.3. Выводы для практики
- •5.4. Неоднозначность кс-грамматик и языков
- •6. Автоматы и преобразователи с магазинной
- •6.1. Основные определения
- •6. 2. Эквивалентность мп-автоматов и кс-грамматик
- •6. 3. Детерминированные мп-автоматы и кс-языки
- •6. 4. Преобразователи с магазинной памятью
- •6. 5. Моделирование мп-преобразователей
5. Свойства автоматных и контекстно-свободных
ЯЗЫКОВ
В этом разделе мы исследуем некоторые из основных свойств А- и КС-языков. Упомянутые здесь результаты образуют малую долю огромного богатства знаний об этих языках. Часть свойств этих языков уже были рассмотрены в разделах 1-4. Ниже мы обсудим общий вид цепочек этих языков, неоднозначность КС-грамматик и КС-языков, некоторые операции, относительно которых замкнуты классы А- и КС-языков.
5.1. Общий вид цепочек а-языков
Мы хотим получить характеристику цепочек А-языков, которая будет полезна для доказательства того, что некоторые языки не являются автоматными. Следующую теорему об общем виде цепочек А-языков называют теоремой о “разрастании”, потому что она в сущности говорит о том, что если дан А-язык и достаточно длинная цепочка в нем, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколько угодно раз (т.е. она “разрастается”), и все полученные таким образом “новые” цепочки будут принадлежать тому же А-языку. С помощью этой теоремы часто приводят к противоречию предположение о том, что некоторый язык является автоматным.
Теорема 5.1. Пусть L - А-язык. Существует такая константа p, что, если L и p , то цепочку можно записать в виде , где p и i L , для всех i .
Доказательство. Если L - конечный язык, то положим константу p больше длины самой длинной цепочки языка L, тогда ни одна из цепочек языка не удовлетворяет условиям теоремы и она верна. В противном случае, пусть M = (Q, , , q0, F) - конечный автомат с n состояниями и L(M) = L. Пусть p = n. Если L и n, рассмотрим последовательность конфигураций, которую проходит автомат M, допуская цепочку . Так как в этой последовательности, по крайней мере, n+1 конфигурация, то найдутся две конфигурации с одинаковыми состояниями. Поэтому, должна быть такая последовательность тактов, что
(q 0, ) (q 1, ) k (q 1, ) (q 2, ) ,
для некоторого q 1 и k n. Отсюда n.
Но тогда, для любого i > 0 автомат может проделать следующую последовательность тактов:
(q 0, i ) (q 1, i )
(q 1, i ) + (q 1, i-1 )
..............
(q 1, 2 ) + (q 1, )
(q 1, ) + (q 1, )
(q 1, ) (q 2, ) .
Для случая i = 0 все еще очевиднее:
(q 0, ) (q 1, ) (q 2, )
Так как L, то и i L, для всех i 0.
Эта теорема, обычно, используется для доказательства того, что некоторые выбранные цепочки не являются цепочками А-языка и, следовательно, не могут быть определены А-грамматиками.
Следствие 5.1. Язык L, состоящий из цепочек x n y n не является автоматным языком.
Допустим, что он автоматный. Тогда, для достаточно большого n цепочка x n y n может быть представлена в виде , причем и i L, для всех i 0.
Если = x...x или = y...y, то 0 L, так как количество символов x и y в цепочке различно. Если = x...xy...y, то = 2 L, так как в цепочке символы x и y будут перемешаны. Полученное противоречие, доказывает, что L - не является А-языком.
Следствие 5.2. Язык арифметических выражений не является А-языком, так как он может содержать произвольное количество вложенных скобок, причем количество открывающих скобок совпадает с количеством закрывающих. Аналогично, не является А-языком любой язык, содержащий вложенные конструкции, типа фигурных скобок в языке C, begin - end, repeat - until и т.п. Каждая конечная А-грамматика, порождающая подобные конструкции, будет выводить и цепочки с неравным количеством открывающих и закрывающих скобок. Тем не менее, анализировать подобные цепочки можно и с помощью автоматного подхода. При этом, в синтаксисе языка допускается произвольное количество открывающих и закрывающих скобок, а контроль их парности возлагается на семантические подпрограммы.