Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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 ;-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.