Я трачу много времени, но до сих пор не могу понять, как это решить. У меня есть ответ. Можете рассказать, как он это придумал?
Существуют ли определенные правила или стандартная конструкция, которым я могу следовать? Я знаю правила объединения и конкатенации, но не в обратном порядке.
Если x является (возможно, неправильной) подстрокой y, то x^r c y можно записать как x^R c wxz, где w и z — произвольные строки над (a+b)*.
Теперь мы можем попытаться «нарезать» строки на этом языке, чтобы увидеть, как они могут быть сгенерированы с помощью CFG. Нестандартная часть этого заключается в том, чтобы убедиться, что x^R и x выходят правильно; остальное банально. Итак, нам нужны некоторые правила, такие как:
S -> aXa | bYb | c
Это дает нам x^R c x. Нам не хватает w и z. w мы можем добавить, поставив после c любую произвольную строку:
S -> aSa | bSb | cA
A -> aA | bA | e
z мы можем получить, изменив S на T и добавив новый S, который производит T, за которым следует что угодно:
S -> TA
T -> aTa | bTb | cA
A -> aA | bA | e
Все, что мы упустили из виду, это то, что |x| > 1. Мы делаем это, изменив T -> cA на две продукции T -> acAa | bcAb. Это дает предложенную грамматику (не единственно правильную, а только одну работающую грамматику) и объясняет, как мы к ней пришли.
