Контекстная грамматика для этого языка

Question

Я работаю над некоторыми материалами для подготовки к тестам и застрял в этой проблеме.

Показать контекстную грамматику для L = {w e {a,b}*: w = wR, и за каждым a сразу следует a b}.

WR это W в обратном порядке. Так, на английском языке, за палиндромом, за каждым "а" следует буква "b", используя любое количество а и b.

До сих пор я получил это для обратной части, но я не могу понять, как включить каждую a за которой следует ab часть, при этом сохраняя свойство палиндрома.

S -> bSb | b | [the empty string]

Любая помощь очень ценится!

Answer 1

Поскольку за каждым "a" должен следовать "b", а результирующее слово должно быть палиндромом (оно одинаково, если его читать с конца до начала), это означает, что перед каждым "a" также должен предшествовать a "б".

Мы начинаем строить слово с середины, растя в обоих направлениях. Правило состоит в том, что когда средняя часть заканчивается (и, следовательно, начинается) буквой "а" (это нетерминал А), за ней должна следовать (и предшествует) буква "b". С другой стороны, когда средняя секция окружена буквой "b" (это нетерминал B), она может расширяться с помощью одной буквы "a" (предыдущий случай) или любого числа цифр "b". Особый случай с равномерно пронумерованными буквами "b" в середине также обрабатывается. Начальный символ S допускает только слова, ограниченные "b" s, поэтому все правила совпадают.

S -> B | [empty]
B -> bAb | bBb | bb | b
A -> aBa | a

Изменить: мое предыдущее решение было неверным, я надеюсь, что это работает сейчас.