Изменения
→Пример
[[Файл:Multi_DKA_result.png]]
Согласно определению:
#*<tex>\delta(\langle s_1, q_2 \rangle, 1) = \langle \delta_1(s_1, 1), \delta_2(q_2, 1) \rangle = \langle t_1, t_{21} \rangle </tex>
#*...
{{Утверждение
|statement=Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex>, построенный как прямое произведение автоматов <tex>A_1</tex> и <tex>A_2</tex> будет их пересечением.
|proof=Возьмем слово <tex>\alpha</tex>, которое допускает автомат <tex>A_1</tex> и автомат <tex>A_2</tex>. Выпишем все состояния в порядке допуска слова <tex>\alpha</tex> автоматом <tex>A_1</tex> {{---}} <tex>a_{11}, a_{12}, ... , a_{1|\alpha|}</tex> и все состояния проходимые при допуске слова автоматом <tex>A_2</tex> {{---}} <tex>a_{21}, a_{22}, ... , a_{2|\alpha|}</tex>. Построим список пар <tex>\langle a_{1i}, a_{2i} \rangle</tex>, где <tex>i = 1, 2, ..., |\alpha|</tex>. Данный список является списком состояний в процессе допуска слова <tex>\alpha</tex> автоматом <tex>A</tex>, так как:
*<tex>\langle a_{11}, a_{21} \rangle = \langle s_1, s_2 \rangle</tex> {{---}} сохраняется стартовое состояние
*<tex>\delta_1(a_{1i-1},c) = a_{1i}</tex>, <tex>\delta_2(a_{2i-1},c) = a_{2i}</tex>, <tex>\delta( \langle a_{1i-1}, a_{2i-1} \rangle, c) = \langle \delta_1(a_{1i-1},c), \delta_2(a_{2i-1},c) \rangle = \langle a_{1i}, a_{2i} \rangle</tex> {{---}} переходы верны
*<tex>a_{1|\alpha|} \in T_1, a_{2|\alpha|} \in T_2, \langle a_{1|\alpha|}, a_{2|\alpha|} \rangle \in T_1 \times T_2 = T</tex> {{---}} сохраняется терминальное состояние
Следовательно автомат <tex>A</tex> допускает слова, которые допускает автомат <tex>A_1</tex> и автомат <tex>A_2</tex>.
Возьмем слово <tex>\beta</tex>, которое не допускает автомат <tex>A_1</tex> или автомат <tex>A_2</tex>, тогда <tex>a_{1|\beta|}</tex> или <tex>a_{2|\beta|}</tex> {{---}} нетерминальное состояние, следовательно <tex>\langle a_{1|\beta|}, a_{2|\beta|} \rangle \notin T_1 \times T_2</tex>.
}}
== Применение ==
Изменив конструкцию, можно получить автомат, допускающий разность или объединение двух языков.
