Question

For a string w, recall that wR denotes the reverse of w, i.e., the string obtained by reversing the order of the symbols of w. For a language L, define S(L)={w∈L:wR∈L}. If L is regular, is S(L) also regular? Prove your claim.

Answer 1

Step-by-step explanation:

One arrangement is recursively (or inductively) characterize a turning around procedure on regular articulations, and apply that procedure on the regular articulation for L. Specifically, given a regular articulation R, reverse(R) is

• a for some a ∈ Σ,

• Σ if R = Σ,

• ∅ if R = ∅,

• (reverse(R1) ∪ reverse(R2)), if R = R1 ∪ R2,

• (reverse(R2) ◦ reverse(R1)) if R =R1◦ R2, or

• (reverse(R1)∗), if R = (R∗1)