2

Given two regular languages $L_1$ and $L_2$ and their respective deterministic finite automaton $A_1, A_2$, I need to construct an automaton $A$ such that $L(A)=(L_1\cup L_2) - (L_1\cap L_2)$ (the symmetric difference of $L_1$ and $L_2$).

I need a formal construction of $A$, based on $A_1$ and $A_2$.

I thought about constructing one automaton for $L_1\cup L_2$, and one for $L_1^C\cup L_2^C$, and than construct their product automaton, but this is very long.

Is there an easier way?

Daniel
  • 558
  • I presume the product automaton's number of states is the product of the number of states in $A_1,A_2$? (That is, its states are ordered pairs of those in the source automata, and both states may change in one step.) – Parcly Taxel May 05 '21 at 12:14

1 Answers1

2

Instead of taking the product between $L_1\cup L_2$ and $L_1^C$ and $L_2^C$, take it between $L_1$ and $L_2$... and then change the accepting states of this (smaller) product automaton to $$\{(s_1,s_2):s_1\text{ is an accepting state of }A_1\text{ or }s_2\text{ is an accepting state of }A_2,\text{ but not both }\}$$ Any word accepted by exactly one of $A_1,A_2$ will be accepted by this new automaton; any word accepted by both will not be. Hence the new automaton accepts the symmetric difference of the two languages.

An analogous construction creates automata whose acceptance or rejection of any word is a Boolean function of the acceptance or rejection of the same word by any number of component languages.

Parcly Taxel
  • 103,344