-1
$\begingroup$

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

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

Is $A_1$ regular?

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

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

$\endgroup$

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.