73
правки
Изменения
м
Нет описания правки
[[Файл: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>.
[[Файл:Multi_DKA_result.png]]
*<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, s_2 \rangle, 1) = \langle \delta_1(s_1, 1), \delta_2(s_2, 1) \rangle = \langle t_1, s_2 \rangle </tex>
*<tex>\delta(\langle s_1, q_2 \rangle, 0) = \langle \delta_1(s_1, 0), \delta_2(q_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>\delta(\langle s_1, t_{21} \rangle, 0) = \langle \delta_1(s_1, 0), \delta_2(t_{21}, 0) \rangle = \langle s_1, q_2 \rangle </tex>...
Действительно, заметим, что только слово <tex>01</tex> допускается автоматом <tex>A_1</tex> и <tex>A_2</tex> одновременно.
== Применение ==
Изменив конструкцию, можно получить автомат допускающий разность или объединение двух языков.
=== Объединение ДКА ===
Необходимо разрешать любую цепочку удовлетворяющую первому или второму автомату, для этого пометим терминальными следующие вершины <tex>T = (T_1 \times T_2) \cup (T_1 \cap Q_2) \cup (Q_1 \cap T_2)</tex>. Полученный автомат удовлетворяет нашим требованиям так как попав в какое-либо состояние из <tex>T_1</tex> или <tex>T_2</tex>, цепочка начинает удовлетворять первому или второму автомату соответственно.
=== Разность ДКА ===
* С помощью данной конструкции можно построить автомат для [[Замкнутость регулярных языков относительно различных операций|пересечения]] [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
