Построить грамматику на язык

Question

L = {a^i b^j c^k | not(i=j=k)}

Подсказка: опишите L как объединение других языков

Я пытаюсь сделать это уже неделю, и просто не могу. Может ли кто-нибудь помочь мне понять?

Редактировать:

Правильно ли говорить:

(i≠j or j≠k) или (i≠j and j≠k and i≠k)

Answer 1

правильно ли сказать: (i ≠ j или j ≠ k) или (i ≠ j и j ≠ k и i ≠ k)

Это не неправильно, говорить это, но это больше, чем вы должны сказать. На самом деле, все, что вам нужно сказать, это первая часть:

(i ≠ j или j ≠ k)

Вторая часть не может быть правдой, если первая часть все равно не была правдой. Отсюда, мы можем далее разбить это:

i j или j k

Это объединение четырех довольно простых контекстно-свободных языков. Если вы получите для них грамматики G1, G2, G3 и G4 с начальными символами S1, S2, S3 и S4 соответственно, вы можете добавить новый начальный символ S и произведения S -> S1 | S2 | S3 | S4, чтобы получить грамматику для их союза.