# Is a language regular if a word is in a regular language but the reverse is not?

$$A_1 = \{ x \mid x \in A , x^R \not\in B\}$$

$$A$$ and $$B$$ are regular over $$\Sigma$$.

Is $$A_1$$ regular?

• Jonathan, please do not deface your posts. Continued vandalism usually results in suspension. – 6005 Mar 20 at 22:15

$$A_1$$ is regular, since regular languages are closed under intersection and complement, and $$A_1 = A \setminus B^{R} = A \cap (B^{R})^{c}$$. To show that the reverse $$B^{R} = \{x^{R} : x \in B\}$$ of a regular language $$B$$ is regular, take some deterministic finite state machine $$M$$ with language $$B$$. Construct a new nondeterministic finite state machine $$M'$$ as follows:
1. Add a new starting node, connect it with $$\varepsilon$$-transitions to every accepting node in $$M$$
2. Make only the original starting node of $$M$$ accepting in $$M'$$
3. Reverse every transition: If there is a transition from state $$s_1$$ to $$s_2$$ with character $$c$$ in $$M$$, add a transition from $$s_2$$ to $$s_1$$ with character $$c$$ to $$M'$$. If there are multiple transitions from a state, the machine can choose among them nondeterministically.
Now $$M'$$ accepts a string $$x^{R}$$ iff $$M$$ accepts $$x$$. This is easy to show: any accepting computation of $$M'$$ of $$x^{R}$$ corresponds to an accepting computation of $$M$$ of $$x$$ and vice versa.