# Finding a grammar that generates a language.

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\}$

Thank you very much

-

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

-
They are the same ... but, as this could help me? – Mark Nov 23 '12 at 21:44
What about the second and second last characters of $x$, and so on? Can you use this observation to help you write a CFG for the language? – donburi Nov 23 '12 at 21:50
Ok, thank you very much! – Mark Nov 27 '12 at 12:52

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 ;-)

-