Лекция 15 Свойства контекстно-свободных языков

Класс контекстно-свободных языков занимает центральное положение в иерархии формальных языков. С одной стороны, этот класс включает в себя важные, но ограниченные семейства языков, такие, как регулярные языки и детерминированные контекстно-свободные языки. С другой стороны, существуют более широкие, нежели класс КС-языков, семейства языков, включающие в себя этот класс. Чтобы изучить соотношения между различными семействами языков, мы исследуем характеристические свойства различных классов языков, в частности, замкнутость относительно тех или иных операций, разрешимость ряда алгоритмических проблем и структурные результаты, к которым относится Лемма о расширении.

Лемма о расширении

В лекции 7 мы доказали Лемму о расширении регулярных языков, которая является эффективным средством для доказательства того, что некоторый язык не регулярен. Подобные леммы о расширении известны и для других классов языков.

Теорема 15.1.

(Лемма о расширении для контекстно-свободных языков.)

Пусть L - бесконечный КС-язык. Тогда существует некоторое целое число m > 0 такое, что для любой строки   L из того, что

  m, следует, что строка  может быть представлена в следующем виде:

 = ,	(15.2)
где   m,	(15.3)
  1,	(15.4)

и так, что для любого i = 0,1, 2, ...

ii  L .

(15.5)

Доказательство.

Рассмотрим ε-свободный язык L, порождаемый грамматикой G без ε-продукций и без цепных продукций. Так как длины строк в правой части продукций ограничены в совокупности некоторым числом k > 0, то длина вывода любой строки   L должна быть не меньше , а так как язык L бесконечен, то, следовательно, в G существуют сколь угодно длинные выводы.

Рассмотрим левосторонний вывод достаточно длинной строки из L. Так как число переменных в грамматике G ограничено, а длина вывода - нет, то, по крайней мере, одна переменная, скажем A, должна встретиться дважды в позиции самого левого нетерминального символа сентенциальной формы. Таким образом, в G должен существовать вывод

S A1 A21 21,

(15.6)

где , ,   T*; ₁, ₂  (N  T)*.

Будем считать, что A является "самой внутренней" повторяющейся левой переменной в данном выводе, подразумевая под этим тот факт, что в выводе

A 

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

В силу нашего предположения о том, что G не содержит ни ε-продукций, ни цепных продукций, ясно, что каждый шаг вывода или порождает новый терминальный символ в сентенциальной форме, или увеличивает ее длину. Отсюда следует, что

₂  1.

Анализируя структуру (15.6), замечаем, что выводы

A A₂

и

A 

возможны в G. А это, в свою очередь, показывает, что в G возможны также выводы

S ₁

и

S i1, i = 1, 2, ...

(15.7)

Вывод (15.6) заканчивается тогда, когда сентенциальная форма превращается в строку терминалов, а это означает, что существуют выводы

₂  ,

₁  ,

где ,   T*. Поэтому из того, что  = , и из (15.7) получаем, что

ⁱⁱ  L.

Так как ₂  1, то отсюда следует выполнение условия (15.4). Покажем, что (15.3) также имеет место. Выберем такое вхождение A в (15.6), для которого в выводе A  отсутствуют повторяющиеся самые левые переменные. Следовательно,  может быть ограничена константой независимо от строки , откуда заключаем, что (15.3) может быть выполнено. Теорема тем самым доказана.

Эта Лемма о расширении полезна для доказательства того, что тот или иной язык не принадлежит классу контекстно-свободных языков. В ней сформулировано необходимое условие принадлежности этому классу, в силу чего эта лемма чаще всего используется в негативном смысле: если для некоторого языка утверждение леммы неверно, то это означает, что этот язык не контекстно-свободный.

Пример 15.8.

Показать, что язык

L = {aⁿbⁿcⁿ  n  0}

не является контекстно-свободным.

Допустим, что язык L контекстно-свободный, и покажем, что это предположение приводит к противоречию. По теореме 15.1. для КС-языка должно существовать натуральное число m с указанными в теореме свойствами. Возьмем строку

a^mb^mc^m  L.

Рассмотрим возможность выбора в ней подстроки . Очевидно, она не может целиком входить ни в подстроку a^m, ни в подстроку b^m, ни в c^m, так как итерация ⁱ и ⁱ сразу нарушает необходимую структуру строки из L. По тем же причинам невозможно выбрать подстроку  так, чтобы она содержала одинаковое количество символов a и b. Значит, остается единственный способ выбора такой подстроки, когда  содержит одинаковое число символов a, b и c. Но это возможно, лишь когда b^m целиком входит в , откуда следует, что

 > m,

а это противоречит условию (15.3). Итак, оказывается, что выбрать подстроку  в строке a^mb^mc^m невозможно, следовательно, язык L не контекстно-свободный.

Пример 15.9.

Рассмотрим язык

L = {  {a, b}*}.

Покажем, что L не является контекстно-свободным.

Рассмотрим строку

a^mb^ma^mb^m  L.

Нетрудно видеть, что при любом представлении этой строки в виде

,

как только мы начинаем итерировать  и , так сразу нарушаем структуру исходной строки и видим тем самым, что существует i такое, что

ⁱⁱ  L.

На основании этого заключаем, что L не может быть КС-языком.