1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ They are the same ... but, as this could help me? $\endgroup$ – Mark Nov 23 '12 at 21:44
  • $\begingroup$ 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? $\endgroup$ – donburi Nov 23 '12 at 21:50
  • $\begingroup$ Ok, thank you very much! $\endgroup$ – Mark Nov 27 '12 at 12:52
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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