Как мы можем построить CFG для контекстно-свободного языка

Создайте CFG для следующего языка: {a^i b^j c^k | j не равно i + k}. Я уже пробовал следующий CFG, но он пропускает некоторые случаи.

S---> AB
A---> ab|aAb|aA|NULL
B---> bc|bBc|cB|NULL

computer-science context-free-grammar pushdown-automaton context-free-language
person UsmanMaan    schedule 11.02.2021    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ваш текущий CFG создаст некоторые строки, которых нет на языке. Например, строка ab — это строка, в которой i = 1, j = 1, k = 0, поэтому i+j = k. Эта строка создается вашей грамматикой.

Один из способов приблизиться к этому — разделить язык на объединение двух языков: {a^i b^j c^k | i+k ‹ j} U {a^i b^j c^k | i+k › j}. Затем мы можем построить CFG для каждого языка. Пусть S — начальное состояние, L — правило грамматики для i+k ‹ j, G — правило грамматики для i+k › j.

Мне было полезно подумать об отмене каждой буквы «b» на «a» или «c» в строке. После того, как вы отменили как можно больше, должны остаться либо какие-то оставшиеся b (i+j ‹ k), либо какие-то оставшиеся a и/или c (i+j > k).

С ---› L | G
L ---› HBF
B ---› b | bB
G ---› aG | ГК | ахф | HFc
H ---› aHb | NULL
F ---› bHc | НУЛЕВОЙ

H производит все строки, в которых есть сбалансированное количество букв a и b, а F создает все строки, в которых есть сбалансированное количество букв b и c. Поэтому думайте о L как о сбалансированном количестве a и b, за которыми следует 1 или более дополнительных b, за которыми следует сбалансированное количество b и C.

Точно так же для G вы можете добавить 1 или более дополнительных букв «а» в начале и/или 1 или более дополнительных «с» в конце. В середине у вас есть сбалансированные числа a и b (отменяющие друг друга) и сбалансированные числа b и c (отменяющие друг друга).

person kera    schedule 13.02.2021