# Is Palindrome subset of a regular language regular?

Suppose we have $$L$$ being a regular language with alphabet $$\Sigma$$, if we define $$M=\{ x \in \Sigma^{*} \mid xx^{R} \in L \}$$, then we know that $$M$$ contains all half copies of palindrome strings of $$L$$, now here comes the question, is $$M$$ regular?

Is it easy to see that when $$L$$ is finite, then $$M$$ is clearly also finite hence regular. However, what if $$L$$ is infinite? I think it will be non-regular and try to pumping lemma but does not work...

• First halves of palindromes and palindromes are very, very different. – gnasher729 Sep 29 '19 at 7:37
• With this sort of question, always try $\Sigma^*$ first. – reinierpost Sep 29 '19 at 12:11
• He’s looking for first halves of palindromes, not complete palindromes, so that example is fine. – gnasher729 Sep 29 '19 at 19:22

The subset of all palindromes in L is obviously not usually regular, take the simple example $$a^*ba^*$$ where the subset of palindromes $$a^nba^n$$ is not regular. But that is not the question. The question is about the set of all left halves of palindromes in L.

Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M:

Given a state S, define succ(S, a) as the state that the FSM will transition to from state S with input a, or nil if there is no transition for a. For a set of states T, define pred(T, a) as the set of states S such that succ(S, a) is not nil and an element of T.

To determine if w is in L, you would start with S = $$S_0$$. Then for every symbol s in w, you replace S with succ(S, s), exiting the loop if S is nil. Finally, w is in L if and only if S ≠ nil and S is an accepting state.

To determine if w is in M, you start with S = $$S_0$$ and T = set of accepting states. Then for every symbol s in w, you replace S with succ(S, s) and T with pred(T, s), exiting the loop if S is nil or T is empty. Finally, w is in M if and only if S ≠ nil and S is an element of T.

Instead of using this algorithm, you can quite easily construct an FSM for M.

• Just bit confused how can we build an FSM for M based on the algorithm – Joe Sep 29 '19 at 17:57
• Look at the algorithm. At every step there is a state which is a combination of S and T, and a clear description how to get from this state to the next. Create a new FSM with these states. – gnasher729 Sep 29 '19 at 19:37