3
$\begingroup$

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

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Just bit confused how can we build an FSM for M based on the algorithm $\endgroup$
    – Joe
    Sep 29, 2019 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, 2019 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.