Контекстная грамматика и обращение

Question

Я создаю контекстную грамматику для генерации этого языка:

{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* }

Я бы определил первые две строки следующим образом:

U -> aU | bU | _
V -> aV | bV | _

И затем скомбинировал их1007 *

S -> UV

Но как я могу выразить обращение как контекстно-свободную грамматику?

Answer 1

Вам необходимо использовать контекстно-независимую грамматику (то, что вы пока представляете, это просто обычная грамматика):

U-> aUa | bUb | a | b | _

Будет соответствовать таким вещам, как "ababa" и«aabaa», но не «aabba».

Я оставляю вам право изменять это в соответствии с вашими потребностями - но имейте в виду, что указанный вами язык может u быть пустой строкой,следовательно, он генерирует все строки в {a,b}*.