Пример языка не являющегося КС-языком

Пусть L= {a^p| p - простое число}. Предположим, что L - КС-язык, тогда существует грамматика G в НФХ, порождающая этот язык. Пусть N - множество нетерминалов этой грамматики и n= |N|.

Применим к этой грамматике основную теорему КС-языков. Тогда существуют l₁=2^n-1 и l₂=2ⁿ, и z= uvwxy. Обозначим |uvwxy|=p> l₁. uvⁱwxⁱyÎL (для любых i³0), обозначим |v_k|= k>0. Можно представить |z_i|=|uvⁱwxⁱy|= |uwy|+|vⁱxⁱ|= p₀+k×i= p.

Если i= p₀, то p₀ - делитель числа p, но по условию p - простое число. Противоречие, следовательно L это не КС-язык.

Вопросы и упражнения

В чем заключается противоречие в данном доказательстве? Что показывает это противоречие?

Проблема конечности языка

Теорема: Пусть грамматика G – КС-грамматика в НФХ и имеет n нетерминалов. l₁= 2^n-1, l₂= 2ⁿ.

Предположим, что zÎL(G) – самая короткая из всех цепочек языка L(G), длина которой |z|£ l₁+l₂.

Доказательство: Пусть z – самая короткая цепочка языка L(G), имеющая длину больше, чем l₁. Предположим, что ее длина |z|>l₁+l₂. Так как z самая короткая цепочка, то не существует цепочек z₁ таких, что l₁<|z|£l₁+l₂.

Так как |z|> l₁+l₂> l₁, применим к этой цепочке основную теорему КСЯ: z= uvwxy:

|vwx|£l₂,

vx¹e,`

"i³0, uvⁱwxⁱyÎL(G).

Возьмем i=0, тогда z₀= uwyÎL(G).

Покажем, что |z0|>l1. |z|= |uvwxy|= |uwy|+|vx|= |uwy|+|vwx|–|w|³ l1+l2, |z0|=|uwy|>l1+l2-|vwx|+|w|³l1+l2–l2+|w|>l1.

Покажем, что |z0|<|z|. |uwy|= |uvwxy|–|vx|<|uvwxy|=|z|.

Таким образом, z – не самая короткая цепочка, что противоречит условиям. ЧТД.

Теорема: Пусть L – КСЯ, порождаемый грамматикой G в НФХ. Язык L(G) бесконечен тогда и только тогда, когда существует цепочка zÌL(G) и l₁<|z|£l₁+l₂, где l₁= 2^n-1, l₂= 2ⁿ, n – мощность множества нетерминалов G.

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

Необходимость: Пусть L(G) – бесконечен, тогда существуют цепочки произвольной длины и найдутся такие zÎL(G), что |z|>l1. Возьмем минимальную такую цепочку z1, тогда по предыдущей теореме l1<|z1|111111111231231123123£l1+l2.

Достаточность: Пусть существует zÌL(G) такая, что l₁<|z|£l₁+l₂. По основной теореме z= uvwxy и z_i= uvⁱwxⁱyÎL(G) для любых i³0. Таких цепочек бесконечное количество, следовательно, язык L(G) бесконечен.

Теорема: Проблема конечности разрешима для КС-грамматики, т.е. существует алгоритм, позволяющий определить конечный или бесконечный язык порождает КС-грамматика.

Алгоритм: Рассмотрим все синтаксикальные формы, выводимые из грамматики G и имеющие длину l₁<k£l₁+l₂. Таких форм будет конечное число. Если среди них есть терминальные цепочки, то язык бесконечен.

Вопросы и упражнения

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