Finding a grammar that generates a language.

Question

Given a string w over an alphabet $\Sigma$ we define symmetric string the string $w^R$ defined as follows:

if $w=\epsilon$ ($\epsilon$ is empty string)

if $w=\sigma x$ with $\sigma\in\Sigma$ and $x\in\Sigma^*$, where $\Sigma^*$ is the set of all strings defined on the alphabet $\Sigma$ (including the empty string).

Then $w^R=x^R\sigma$.

Clearly $(w^R)^R=w$.

Example: if $w=road$ then $w^R=daor$.

In class, my professor gave to solve the following exercise.

Exercise: Define the grammar that generates the language $\{x|exist\ \ w \ \ such\ \ that\ \ x=ww^R\}$

Any suggestions please?

Thank you very much

Answer 1

Hint: If $x$ is in the language, what can you say about the first and last characters of $x$?

Answer 2

Hint:

• Create grammar that creates expressions of the form $(^n)^n$, that is $n$ nested parentheses.
• Create grammar that creates expressions as the above, but there are two types of brackets: round $($ and square $[$, and of course right-symbols $)$ and $]$ has to match appropietly, eg. $([()])$ is ok, but $([)]$ is not.

Hope that helps ;-)