Пусть L(a) обозначает язык автомата A, т.е. то множество цепочек, которое этим автоматов допускается.

Исходная задача сводится к двум:

1. Для автомата B получить автомат, который допускает -L(B), т.е. дополнение языка L(B). Эта задача стандартная, надо просто инвертировать состояния исходного автомата: каждое допускающее сделать недопускающим, а каждое недопускающее -- допускающим. Тогда, любая цепочка, которая недопускается автоматом B, станет допускаться автмоматом -B. с другой стороны, если цепочка допускается автоматом B, то при ее чтении он переходит в недопускающее состояние, а значит, в недоспускающее состояние автомата -B. Иначе говоря, дополнение автматного языка является автоматным языком.

2. Найти автомат, который допускает пересечение языков автоматов A и -B. Основная идея такого автомата -- это запуск параллельно двух автоматов и допуск цепочки только тогда, когда автматы при чтении цепочки одновременно переходят в допускающие состояния. Но понятие "параллельно" в контексте автоматов и их языков непонятно, надо сконструировать новый автомат, который инкапсулирует идею параллельного запуска в себе. Для этого вводят автомат, который работает не на одной цепочке, а на цепочке из пар символов. Пара в данном случае обозначает как раз, что автоматы запускаются на двух цепочках одновременно. Пары -- это декартово произведение, т.е. мы берем цепочки над алфавитом Sigma(A) X Sigma(B), где Sigma(A) и Sigma(B) -- алфавиты языков соответствующих автоматов. Состояния автомата -- пары состояний исходных автоматов, допускающие из них -- пары из допускающих состояний. На вход этому автомату подается последовательность пар символов, но нам необходимо выполнить требование, что пары в этой цепочке должны формироваться из одних и тех же символов, тогда это будет соответстовать нашей идее запуска двух автоматов на одной цепочке. Т.е. из всех пар мы должны выбрать только те, у которых первый и второй компоненты равны, т.е. диагональ декартова произведения. Эта самая диагональ есть то же самое, что и сама цепочка.