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

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

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

wR - это w в обратном порядке. Итак, в английском языке - палиндром, где за каждой буквой «а» следует «б», используя любое количество «а» и «б».

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

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

Любая помощь приветствуется!


regular-language context-free-grammar automata automata-theory
person ContextFreeBallin    schedule 24.02.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

person buc    schedule 24.02.2011
comment
Я считаю, что это работает, я очень ценю подробное объяснение, так как это было то, что я искал больше, чем просто ответ. - person ContextFreeBallin; 24.02.2011