Como autômatos XOR?

Digamos que temos três DFAs. Nós sabemos como OR, AND, ou NOT eles. Mas como alguém os XOR? Não há uma única menção a isso online.

$x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) (\neg ((x|y)(\neg x|y))|z)$ . Isso é muito complicado e demorado para desenhar. Não existe outro caminho?

Obrigado por tomar o tempo!

Observe que a construção para a interseção e união ("e" e "ou") de dois autômatos é exatamente a mesma, exceto pela definição de quais estados estão aceitando. O mesmo princípio se aplica a qualquer combinação booleana de qualquer conjunto finito de linguagens: use a construção do produto e a definição apropriada de quais estados devem ser aceitos.

Como as três máquinas são todas determinísticas, a operação combinada não é nada complicada. Execute as máquinas em paralelo, usando uma construção direta do produto como a que também é usada para interseção e, em cada XOR de três estados, a presença de estados finais para verificar se o novo estado do produto XOR deve ser aceito.

Como você está trabalhando apenas com DFAs, é possível XOR dois autômatos construindo o produto cruzado dos dois autômatos e, em seguida, assumindo como estados de aceitação aqueles pares de estados dos quais um estado é um estado de aceitação, mas não ambos.

Observe que essa construção funciona apenas para DFAs em que cada estado possui exatamente um estado sucessor para cada símbolo do alfabeto. Isso garante que você sempre alcance um estado ao simular o autômato e a aceitação de uma palavra depende apenas se esse estado é um estado final ou não. Às vezes, os DFAs são definidos para que cada estado tenha no máximo um estado sucessor para cada símbolo do alfabeto. Nesse caso, a construção acima não funciona mais, porque agora existe uma segunda razão pela qual uma palavra não é aceita: com algumas palavras, nenhum estado é atingido.