Рассмотрим строку a ^ pb ^ pc ^ pd ^ p. Эта строка обязательно на языке. Если бы язык был регулярным и для него существовала регулярная грамматика, то он удовлетворял бы требованиям леммы о накачке для регулярных языков: а именно, приведенная выше строка могла бы быть записана как uvx, где | uv | <= p, | v | > 0 и для всех натуральных чисел n u (v ^ n) x также есть в языке. Есть семь случаев для того, что содержит v: просто a; а и б; просто б; б и в; просто c; c и d; или просто d. В любом случае, прокачка v изменит количество экземпляров одного вида символа, но не количество экземпляров соответствующего символа (тот, который требует язык, должен быть точно таким же частым). Таким образом, язык не может быть регулярным.
Аналогично, лемма о перекачке для контекстно-свободных языков требует, чтобы указанная выше строка была записана как uvxyz, где | vxy | <= p, | vy | > 0 и для всех натуральных чисел n u (v ^ n) x (y ^ n) z также является строкой языка. Здесь мы получаем в точности те же случаи, что и выше, и приходим к точно такому же выводу: язык не может быть контекстно-независимым.
Учитывая все это, мы могли бы просто нацеливаться на неограниченную грамматику (возможно, можно было бы получить контекстно-зависимая грамматика для этого языка, но это не требуется). Нам нужно одинаковое количество a и c и одинаковое количество b и d, и мы хотим, чтобы они были в алфавитном порядке. Мы можем начать так:
S -> ACS | BDS | T
Это позволяет нам получать строки с тем же номером A, что и C, и тем же номером B, что и D, заканчивающимися на T. Затем нам нужны строки правила, позволяющие размещать символы A, B, C и D в правильном порядке:
BA -> AB
CA -> AC
DA -> AD
CB -> BC
DB -> BD
DC -> CD
Наконец, нам нужен способ конвертировать нетерминальные A, B, C и D к терминалам a, b, c и d таким образом, что он не может работать, если все они не в порядке. Мы можем использовать T (и несколько других символов, которые будут представлены в ближайшее время) для перемещения справа налево, преобразовывая, как мы go:
DT -> Td
CT -> Uc
BT -> Vb
AT -> Wa
T -> e
CU -> Uc
BU -> Vb
AU -> Wa
U -> e
BV -> Vb
AV -> Wa
V -> e
AW -> Wa
W -> e
Нетерминалы T, U, V и W позволяют преобразовывать AD, A- C, AB и A до ad, a- c, ab и a соответственно. Мы также можем избавиться от этого символа маркера в любое время. Единственный способ удалить все нетерминалы и получить строку терминалов (то есть сгенерировать строку в соответствии с этой грамматикой) - это прокручивать справа налево, преобразовывая все встречающиеся символы и, наконец, использовать любое из правил X -> e нужен для устранения маркера. Это может работать, только если символы были преобразованы в порядке убывания справа налево, поэтому они должны быть в порядке возрастания слева направо, как требуется. Поскольку продукция для S вводит A, C и B, D в согласованных парах, это требование также выполняется.