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

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

| cite | improve this answer | |
  • $\begingroup$ Just bit confused how can we build an FSM for M based on the algorithm $\endgroup$ – Joe Sep 29 '19 at 17:57
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Sep 29 '19 at 19:37

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.