Итак, у меня есть этот язык L={a^i b^2j+1 / i<>j}, и я должен создать контекстно-свободную грамматику на его основе, не могли бы вы помочь мне проиллюстрировать шаги для этого.
Пока у меня это:
S-->aS/aBbb
B-->bB/b/e(empty)
но я не уверен, что это правильно, пожалуйста, помогите мне понять это.
Для языков с ограничением «не равно» самый простой подход обычно состоит в том, чтобы сначала найти грамматику, которая соответствует языку с ограничением «равно», а затем изменить ее, чтобы требовать больше одного из элементов.
В этом случае у нас есть несколько токенов a, за которыми следует нечетное количество токенов b, где ограничение на количество каждого. Для равного случая это становится просто
S → aSbb | б
один b с таким же количеством a и парами b, обернутых вокруг него.
Чтобы сделать его неравным, нам нужно добавить либо дополнительные a, либо дополнительные пары B, но не то и другое одновременно:
S → AS' | S'B
S' → aS'bb | б
А → Аа | a
B → Bbb | бб
abbb, который имеет i == j == 1, нарушая ограничение (S-›aBbb, B-›b) - person Chris Dodd schedule 12.06.2014