Могут ли эти шаблоны соответствовать регулярному выражению или контекстно-свободной грамматике?

Question

Это упражнение компилятора.Нас спрашивают, можно ли сопоставить следующие шаблоны с регулярными выражениями или контекстно-свободной грамматикой:

1. n 'a' с последующим n 'b', например, 'aabb'
2. палиндром, например, 'abbccbba'
3. n 'a', затем n 'b', затем n 'c', например 'aabbcc'

Обратите внимание, что n может быть любым положительным целым числом.(В противном случае это слишком просто)

Только 3 символа 'abc' могут появиться в тексте для разбора.

Я запутался, потому что, насколько я вижу, ни один из этих шаблонов не может бытьописывается регулярными выражениями и контекстно-свободной грамматикой.

Answer 1

Критический вопрос: сколько и какой памяти вам нужно?

В случае проблемы 1 вам нужно каким-то образом отслеживать количество a терминалов во время анализаклеммы b.Поскольку вы знаете, что вам нужен один на один, стека явно достаточно (вы можете положить a в стек и вытолкнуть по одному с каждым b).Так как автомат с выталкивающей силой эквивалентен CFG по выразительной мощности, вы можете создать CFG для задачи 1.

В случае задачи 2 метод, который КПК использует в задаче 1, должен наводить на мысль о техникеВы могли бы использовать для задачи 2. КПК могут построить стек из первой половины ввода, а затем вытолкнуть его, когда появится его обратное.

В случае задачи 3, если вы используете технику стека дляподсчитав количество a терминалов и b терминалов, это все хорошо, но что случилось с вашей памятью стека?Было ли этого достаточно?Нет, вам нужно было бы хранить число a s где-то еще, поэтому CFG не может выразить эту грамматику.

Answer 2

Вот попытка простого CFG для задачи 2 (она проверяет пустой ввод, но вы поймете идею):

S -> a S a
S -> b S b
S -> c S c
S -> ɛ