1
$\begingroup$

Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

Generate a cfg of $L_n$

For n = 1, 2, 3


Informally, x is in $L_n$ means some palindrome of at least length n is a substring of x that occurs exactly at the midpoint of x.

for $n = 1$

$S \to 0S0 | 1S1 | 0S1 | 1S0|0 | 1 | 00 | 11$

for $n = 2$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | \epsilon$

for $n = 3$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | 00 | 11 | \epsilon$

would this be right?

Say I changed it to $|y| > |z|$ or $|y| < |z|$ how would this differ?

$\endgroup$
  • $\begingroup$ This CFG doesn't generate $001 \in L_1$. $\endgroup$ – Yuval Filmus Nov 12 '18 at 8:07
  • 2
    $\begingroup$ What don't you understand? What would you like us to explain? What level should an answer be written at? $\endgroup$ – David Richerby Nov 12 '18 at 13:31
1
$\begingroup$

When $n=1$, the language $L_1$ consists of all words of the form $ywz$, where $|y|=|z|$ and $w$ is a non-empty palindrome. We can generate all non-empty palindromes as follows: $$ P \to 0P0 \mid 1P1 \mid 0 \mid 1 \mid 00 \mid 11 $$ Given that, we can generate $L_1$ by capturing also the outer part: $$ S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid P $$ For larger $n$, all we need to change is the "base cases" for $P$.

Further observation reveals that we can actually assume that $|w| \leq 2$ (for $n = 1$), and so we can use alternatively the following productions for $P$: $$ P \to 0 \mid 1 \mid 00 \mid 11 $$ This allows us to eliminate $P$ from the grammar, reaching the following grammar: $$ S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid 0 \mid 1 \mid 00 \mid 11 $$ These steps can also be extended to larger $n$.

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