Доказательство. Пусть языки U1и U2 распознаются автоматами

Пусть языки U ₁и U ₂ распознаются автоматами

 ₁ = (A, Q ₁, j₁, q ₀, D ₁) и  ₂ = (A, Q ₂, j₂, q ₁, D ₂).

Построим конечный автомат Á, который функционирует из своего начального состояния так же, как и два параллельно работающих автомата Â ₁ и Â ₂.

Определим автомат Á как (A, Q ₁ Q ₂, j, (q ₀, q ₁), D), где D обозначает множество состояний, которое будет выбираться так, чтобы обеспечить распознавание множеств U ₁È U ₂, U ₁Ç U ₂, и U ₁\ U ₂.

Состояния Á - это пары (q _i, q _j), где q _i Î Q ₁ и q _j Î Q ₂. Начальным состоянием Á является состояние (q ₀, q ₁). Функция перехода j представляет собой пару функций (j₁, j₂), каждая из которых определяет значение соответствующей компоненты состояния Á. То есть, если в момент времени t автомат находится в состоянии (q¢ (t), q² (t)), то значение состояния Á в момент t+1 равно (j₁(x (t), q¢ (t)), j₂(x (t), q² (t))).

Тогда автомат Á из начального состояния (q ₀, q ₁) распознает множество U ₁ È U ₂, если в качестве множества распознающих состояний D выбрано множество

D ₁ Q ₂ È Q₁ D ₂.

Действительно, при переработке произвольного входного слова из начального состояния (q ₀, q ₁) компоненты состояния автомата Á изменяются так же, как состояния автоматов Â ₁ и Â ₂, когда эти автоматы перерабатывают из состояний q ₀ и q ₁ соответственно.

Поэтому Á заканчивает переработку в состоянии из D тогда и только тогда, когда автомат Â ₁ заканчивает переработку в состоянии из D ₁ или Â ₂ заканчивает переработку этого же слова в состоянии из D ₂.

То есть U ₁ È U ₂ Á заканчивает переработку этого слова в состоянии из множества D ₁ Q ₂ È Q ₁ D ₂.

Аналогично можно показать, что если в качестве множества распознающих состояний взять D ₁ D ₂, то автомат Á из начального состояния (q ₀, q ₁) распознает U ₁Ç U ₂.

Множество U ₁\ U ₂ распознается конечным автоматом Á, для которого D = D ₁ (Q ₂ \ D ₂).

Если множество слов U распознается автоматом

 = (A, Q, j, q ₀, D), то A ^* \ U распознается автоматом

(A, Q, j, q ₀, Q \ D).