Доказать, что не существует КС-грамматики, в которой были бы выводимы слова вида 00..0011..1122..22, в которых числа нулей, единиц и двоек равны, и только они.

Указание. Докажите следующую лемму о произвольной КС-грамматике: для любого достаточно длинного слова F, выводимого в этой грамматике, существует такое его представление в виде ABCDE, что любое слово вида AB..BCD..DE, где B и D повторены одинаковое число раз, также выводимо в этой грамматике. (Это можно установить, найдя нетерминальный символ, оказывающийся своим собственным «наследником»в процессе вывода.)

Нетерминальный символ можно рассматривать как «родовое имя»для выводимых из него слов. В следующем примере для наглядности в качестве нетерминальных символов использованы фрагменты русских слов, заключенные в угловые скобки. (С точки зрения грамматики каждое такое слово —один символ!)

Пример 3. Алфавит:

терминалы: + * ( ) x нетерминалы: <выр>, <оствыр>, <слаг>, <остслаг>, <множ> правила:

<выр> ‑> <слаг> <оствыр> <оствыр> ‑> + <выр> <оствыр> ‑> <слаг> ‑> <множ> <остслаг> <остслаг> -> * <слаг> <остслаг> -> <множ> ‑> x <множ> ‑> ( <выр> )

Согласно этой грамматике, выражение (<выр>) —это последовательность слагаемых (<слаг>), разделенных плюсами, слагаемое —это последовательность множителей (<множ>), разделенных звездочками (знаками умножения), а множитель —это либо буква x, либо выражение в скобках.