HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

How to XOR automata?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
xorautomatahow

Problem

Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online.

$x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) (\neg ((x|y)(\neg x|y))|z)$. This is way too complicated and time consuming to draw. Isn't there another way?

Thank you for taking the time!

Solution

Note that the construction for the intersection and union ("and" and "or") of two automata is exactly the same, except for the definition of which states are accepting. The same principle applies to any Boolean combination of any finite set of languages: use the product construction and the appropriate definition of which states should be accepting.

Context

StackExchange Computer Science Q#33018, answer score: 10

Revisions (0)

No revisions yet.