73
правки
Изменения
м
Пример
* <tex>\delta(\langle q_1, q_2 \rangle, c) = \langle \delta_1(q_1, c), \delta_2(q_2, c) \rangle.</tex>
}}
== Пример ==
[[Файл:Multi_DKA_source.png]]
Возьмем автомат <tex>A_1 = \langle \Sigma = \lbrace 0, 1 \rbrace, Q_1 = \lbrace s_1, t_1 \rbrace, s_1, T_1 = \lbrace t_1 \rbrace, \delta_1 \rangle</tex> допускающий слова <tex>(0)^*1</tex>, и автомат <tex>A_2 = \langle \Sigma = \lbrace 0, 1 \rbrace, Q_2 = \lbrace s_2, q_2, t_{21}, t_{22} \rbrace, s_2, T_2 = \lbrace t_{21}, t_{22} \rbrace, \delta_2 \rangle</tex> допускающий слова <tex>(01)^*</tex>.<br>
[[Файл:Multi_DKA_result.png]]
Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex> будет их пересечением.
Согласно определению:
*<tex>\Sigma = \lbrace 0, 1 \rbrace</tex>
*<tex>Q = \lbrace \langle s_1, s_2 \rangle, \langle s_1, q_2 \rangle, \langle s_1, t_{21} \rangle, \langle s_1, t_{22} \rangle, \langle t_1, s_2 \rangle, \langle t_1, q_2 \rangle, \langle t_1, t_{21} \rangle, \langle t_1, t_{21} \rangle \rbrace</tex>
*<tex>s = \langle s_1, s_2 \rangle</tex>
*<tex>T = \lbrace \langle t_1, t_{21} \rangle, \langle t_1, t_{22} \rangle \rbrace</tex>
*<tex>\delta(\langle s_1, s_2 \rangle, 0) = \langle \delta_1(s_1, 0), \delta_2(s_2, 0) \rangle = \langle s_1, q_2 \rangle </tex>
*<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>
Действительно, заметим, что только слово <tex>01</tex> допускается автоматом <tex>A_1</tex> и <tex>A_2</tex> одновременно.
== Применение ==
* С помощью данной конструкции можно построить автомат для [[Замкнутость регулярных языков относительно различных операций|пересечения]] [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
