а) При автомат M=<Σ, Q, q0, , Φ> распознает язык L = L1 L2.
б) При F∩={(q, p) | q F1 и p F2} автомат M =< Σ, Q, q0, F∩,Φ > распознает язык L = L1∩ L2.
в) При F\= {(q, p) | q F1 и p F2} автомат M =< Σ, Q, q0, F\, Φ > распознает язык L = L1\ L2.
Доказательство этой теоремы непосредственно выводится из следующего утверждения.
Лемма 2. Для любых двух состояний (q, p) и (q’, p’) автомата M и любого входного слова w слово w переводит (q, p) в (q’, p’) в автомате M тогда и только тогда, когда оно переводит q в q’ в автомате M1 и p в p’ в автомате M2.
Лемма устанавливается индукцией по длине слова w.
Следствие. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.