Как найти грамматику для языка, где один символ не повторяется столько раз, сколько сумма других?

Question

Я пытаюсь найти грамматику, которая генерирует язык

L = {a ⁱ b ^j c ^k | j ≠ i + k}

Однако мне трудно понять, как создать грамматику, которая делает это. Я также не могу найти информацию в Интернете о борьбе с неравенством в контекстно-свободной грамматике.

Мои первые мысли - разделить это на:

L = {a ⁱ b ^j c ^k | j | {a ⁱ b ^j c ^k | j> i + k}

Даже советы и идеи, которые, по вашему мнению, могут быть очевидны, будут высоко оценены.

Answer 1

Ваш подход хорош - разбейте его на более простые подзадачи, основанные на дизъюнкции в «не равны», а затем присоединитесь к ним:

S -> L | G

Теперь, как нам сделать грамматику, чтобы дать ^ i b ^ j c ^ k, где j L -> BC B -> aBb | e C -> bCc | e Теперь, как мы можем изменить это, чтобы обеспечить j aB и C -> Cc, чтобы разрешить больше a и c, но не применять их. Мы можем применить хотя бы одно из двух условий, изменив L -> BC, чтобы учесть обе возможности (мы могли бы добавить L -> aBCc для ясности, но это не обязательно).

L -> aBC | BCc
B -> aBb | aB | e
C -> bCc | Cc | e

Для G мы начинаем так же:

G -> DE
D -> aDb | e
E -> bEc | e

Теперь нам нужно принудительно добавить дополнительный b. Мы можем сделать это, разрешив больше b правил для D и E, а затем потребовав это в правиле для G:

G -> DbE
D -> aDb | Db | e
E -> bEc | bE | e

Сочетание этих слов должно дать грамматику для желаемого языка:

S -> L | G
G -> DE
D -> aDb | e
E -> bEc | e
G -> DbE
D -> aDb | Db | e
E -> bEc | bE | e

Answer 2

Решив два неравенства и объединив их в одну грамматику, я смог решить эту проблему.

L = {a ⁱ b ^j c ^k |j> i + k} | {a ⁱ b ^j c ^k |j Первый {a ⁱ b ^j c ^k |j> i + k}:

Считайте ^ нулевым символом.

G -> aA  
A -> aA | aAc | B  
B -> aB | aBb | ^  

Тогда {a ⁱ b ^j с ^к |j L -> Cc C -> Cc | aCc | D D -> Db | aDb | ^ И чтобы объединить их, просто объедините их:

S -> G | L 

Чтобы вывести просто сумму j и k, а затем определить, какой путь G или L следовать,Я разработал пару примеров дериваций ниже: