Контекстная лемма прокачки

Question

Является ли следующий языковой контекст бесплатным?

L = {a^i b^k c^r d^s | i+s = k+r, i,k,r,s >= 0}

Я пытался придумать грамматику без контекста, чтобы сгенерировать это, но не могу, поэтому я предполагаю, что она не является контекстно-свободной. Что касается моего доказательства от противоречия:

Предположим, что L не зависит от контекста,

Пусть p - постоянная, определяемая леммой прокачки,

Выберите строку S = a^p b^p c^p d^p, где S = uvwxy

Как | VWX | <= p, то самое большее vwx может содержать два разных символа:

случай а) vwx содержит только один тип символа, поэтому uv^2wx^2y приведет к i+s!= k+r

случай б) vwx содержит два типа символов:

i) vwx состоит из b и c, поэтому uv^2wx^2y приведет к i+s!= k+r

Теперь моя проблема в том, что если vwx состоит из a и b, или c и d, то их накачка не обязательно нарушит язык, так как i и k или s и r могут увеличиться в унисон, что приведет к i+s == k+ г.

Я делаю что-то не так или это язык без контекста?

Answer 1

Я не могу придумать CFG для генерации этого конкретного языка, но мы знаем, что язык не зависит от контекста, если его распознают некоторые автоматы.

Разработка такого КПК не будет слишком сложной. Несколько идей для начала: мы знаем, что i + s = k + r. Эквивалентно, ik-r+s = 0 (я написал это в таком порядке, так как это порядок, в котором они появляются). Суть проблемы в том, чтобы решить, что делать со стеком, если (k+r)>i.

Если вы не знакомы с КПК или не можете использовать их для решения проблемы, по крайней мере, теперь вы знаете, что это без контекста.

Удачи!

Answer 2

Вот грамматика, которая принимает этот язык:

A -> aAd
A -> B
A -> C
B -> aBc
B -> D
C -> bCd
C -> D
D -> bDc
D -> ε