Peter Linz Exercise 5.1 #11

Question

Find a context free grammar for ∑ = {a,b} for the language 

L = { aⁿ ww^R bⁿ : w ∈ ∑^*, n>=1 } 

I have worked out the following set of productions

S--> aSb | aAb //generates aⁿbⁿ

A--> aXa | bXb | ∈ (Generates ww^R which can be considered as string starting and ending with same symbol).

X--> aX | bX | ∈

are my productions correct?

Answer 1

$$\begin{align*} &A\rightarrow aAb|{\color{red}{a}}X{\color{red}{b}} \\ &{\color{blue}{X}}\rightarrow a{\color{blue}{X}}a|b{\color{blue}{X}}b|\epsilon \\ \end{align*}$$