Как я могу написать свою контекстно-свободную грамматику?

Question

Я пытаюсь написать CFG по алфавиту Σ = {a,b} для всех слов, начинающихся и заканчивающихся таким же числом a, с по крайней мере одним b посередине.

Теперь я понимаю основную концепцию CFG, переменные, правила производства и т. Д. К сожалению, у меня закончились идеи для написания вышеупомянутого CFG. Все, что я получил до сих пор

S → aYXYa 
X → XbX | b | λ 
Y → ??? 

Я думаю что правила производства S и X даст мне строку с двумя ** a ** с обеих сторон, как многие ** b ** в середине, как мне хотелось бы. Тем не менее, я не уверен, как я могу также положить столько ** ** a ** с обеих сторон ** b ** с, убедившись, что точно такое же количество ** a ** s с каждой стороны ,

Любые предложения, решения были бы высоко оценены. Благодарю.

Answer 1

 
S → aSa | B 
B → b | bB 

Это должен быть CFG, который вы ищите. Всякий раз, когда вы имеете дело с одним и тем же в начале и в конце, помните, что вы не можете гарантировать, что тот же var будет заполнен таким же образом. Таким образом, вы должны сделать это явным.

Answer 2

Как бывший профессор, который раньше преподавал этот класс, я не дам вам ответа. Я, однако, дам вам подсказку:

У вас есть правильная идея разбить ее на две части: a и остальные. Однако вы не делаете ни одного из них правильно.

Сначала попробуйте написать: a ⁿ ba ⁿ затем оттуда оттуда.

Надеюсь, что это поможет.

Answer 3

Это было время, так как мой старшекурсник дней CS, но это выглядит разумно:

S -> Asa | bX

X -> bX | E

В принципе, вы начинаете с S и добавляете столько пар, сколько хотите, а затем переключаетесь на X и добавляете столько же, сколько хотите.