Is the language consisting of the bitwise XOR of elements of two regular languages still a regular language?

For example, consider $$L=\{ x \operatorname{xor} y \mid x \in A, y \in B, |x|=|y| \},$$ where $A$ and $B$ are both regular languages.

Can I say that $L$ is also a regular language?

  • 2
    $\begingroup$ What have you tried so far? $\endgroup$
    – ShyPerson
    Apr 27 '20 at 4:39
  • $\begingroup$ @ShyPerson since A is regular, then i think x is also regular too, because regular language are closed in AND and OR and COMPLEMENT, then x xor y is also regular $\endgroup$
    – Lix
    Apr 27 '20 at 5:10
  • $\begingroup$ What is the alphabet of your languages? What is the definition of x xor y ? $\endgroup$
    – J.-E. Pin
    Apr 27 '20 at 6:47
  • $\begingroup$ @J.-E.Pin {0,1}* $\endgroup$
    – Lix
    Apr 27 '20 at 7:10

You can show that $L$ is regular by using an NFA. Briefly, the NFA is going to simulate DFAs for $A$ and for $B$, guessing the decomposition of the input into $x \oplus y$ as it goes. The same works for any other operation such as AND and OR.

In more detail, suppose that we are given DFAs for $A,B$:

  • Sets of states $Q^A,Q^B$.
  • Initial states $q_0^A,q_0^B$.
  • Final states $F^A,F^B$.
  • Transition functions $\delta^A,\delta^B$.

We construct an NFA for your language $L$ as follows:

  • Set of states is $Q^A \times Q^B$.
  • Initial state is $\langle q_0^A,q_0^B \rangle$.
  • Final states are $F^A \times F^B$.
  • Transition function is $$ \begin{align} &\delta(\langle q^A,q^B \rangle, 0) = \{\langle \delta^A(q^A,0), \delta^B(q^B,0) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,1) \rangle \}, \\ &\delta(\langle q^A,q^B \rangle, 1) = \{\langle \delta^A(q^A,0), \delta^B(q^B,1) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,0) \rangle \}. \end{align} $$ You can prove inductively that $$ \delta(\langle q^A,q^B \rangle, w) = \{ \langle \delta^A(q^A,x), \delta^B(q^B,y) \rangle \mid x \oplus y = w \}, $$ from which the correctness of the construction easily follows.

Consider the one-state (non determinstic) transducer $\tau$ from $\{0,1\}^*$ to $\{0,1\}^* \times \{0,1\}^*$ defined by the transitions $0 \to (0,0)$, $0 \to (1,1)$, $1 \to (0,1)$ and $1 \to (1,0)$. Now $$ \tau^{-1}(A \times B) = \{u \in \{0,1\}^* \mid \tau(u) \cap (A \times B) \not= \emptyset \}= L $$ Since $A$ and $B$ are regular, $A \times B$ is a recognizable subset of the monoid $\{0,1\}^* \times \{0,1\}^*$ and thus $L$ is regular.


Assume we have finite state machines for languages X and Y. Let f(a, b) be any function of two symbols x and y, and let F(A, B) for strings A, B of same length be the string consisting of the symbols f(a_i, b_i). Let g(c) be the set of all pairs (a, b) such that f(a, b) = c. And we want the language L = { F(A, B): A, B have same length, A is in X, B is in Y }.

We try to build a finite state machine for L.

If we process a symbol c, two state machines for X and Y would process any pair of symbols (a, b) where f (a, b) = c, in other words any pair of symbols (a, b) element of g(c).

So if these two state machines were in states S_i and T_j, they would transfer into any pair of states that the first machine would transfer to with input a, and the second would transfer to with input b.

This tells us what the states of the state machine for L should look like: Each state for L is a set of pairs (S_i, T_j) where S_i, T_j) are states of the state machines for X and Y. The initial state is { (S_0, T_0)} }. A state is accepting if any of the pairs (S_i, T_j) consists of two accepting states.

To calculate the state we transition to from one state with input c: Let the state be the set { (S_i, T_j) }. Let { (a_n, b_m) } be the set of pairs with f(a_n, b_m) = c. Then the new state is the set of all states that S_i transitions to with input a_n, and S_j transitions to with input b_m.

Yours is a special case. Since we can construct a state machine, it's regular. If X and Y have I and J different states, then there are I*J pairs of states, and $2^{I*J}$ different sets of pairs of states, which is the maximum number of states needed for L.


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.