Теорема 1. а) При автомат M=<Σ, Q, q0, , Φ> распознает язык L = L1L2

а) При автомат M=<Σ, Q, q0, , Φ> распознает язык L = L₁ L₂.

б) При F∩⁼{(q, p) | q F₁ и p F₂} автомат M =< Σ, Q, q₀, F∩^,Φ > распознает язык L = L₁∩ L₂.

в) При F_\= {(q, p) | q F₁ и p F₂} автомат M =< Σ, Q, q₀, F_\, Φ > распознает язык L = L₁\ L₂.

Доказательство этой теоремы непосредственно выводится из следующего утверждения.

Лемма 2. Для любых двух состояний (q, p) и (q^’, p^’) автомата M и любого входного слова w слово w переводит (q, p) в (q^’, p^’) в автомате M тогда и только тогда, когда оно переводит q в q^’ в автомате M₁ и p в p^’ в автомате M₂.

Лемма устанавливается индукцией по длине слова w.

Следствие. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.

Дата добавления: 2014-01-05