[Solved]: Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes

Problem Detail: 

This is an extension of a previous question asked by a different user earlier:

Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying

1. $y'x' = xy$.
2. $y'u'x' = xuy$.
3. $y'v'x' = xvy$.
4. $y'w'x' = xwy$.
5. $y'v'u'x' = xuvy$.
6. $y'w'v'x' = xvwy$.

Then $y'w'v'u'x' = xuvwy$.

Now, using the above result, show that a regular language $L$ recognized by an NFA $M$ consists purely of palindromes if and only if $\{x \in L : |x| < 3n\}$ consists purely of palindromes, where $n$ is the number of states in $M$. When I say that some language "consists purely of palindromes," I mean that every string in the language is a palindrome.

Asked By : David Smith

Answered By : Yuval Filmus

Suppose that $L$ satisfies your condition. We prove that $L$ accepts only palindromes by induction on the size of the word.

Let $a \in L$ be a word of length at least $3n$. Tracing some accepting computation of $a$ on the given NFA, some state must repeat at least four times, so we can write $a=xuvwy$ (where $u,v,w$ are non-empty), where the state after reading $x,u,v,w$ is the same, say $s$. So $u,v,w$ all have a computation that goes from $s$ to $s$. This implies that the NFA also accepts $xy,xuy,xvy,xwy,xuvy,xvwy$. By induction, all of these are palindromes, and so they satisfy the prerequisites of the lemma with $x',u',v',w',y'$ being obtained by reversing the unprimed string. The lemma then implies that $a$ itself is a palindrome.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32618

 Ask a Question

 Download Related Notes/Documents