Изменения

Перейти к: навигация, поиск

Прямое произведение ДКА

2047 байт добавлено, 20:50, 10 марта 2018
Нет описания правки
[[Файл:Multi_DKA_result.png]]
 
Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \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>\ldots</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},\ldots, a_{1|\alpha|}</tex> и все состояния проходимые при допуске слова автоматом <tex>A_2</tex> {{---}} <tex>a_{21}, a_{22},\ldots, a_{2|\alpha|}</tex>.Построим список пар <tex>\langle a_{1i}, a_{2i} \rangle</tex>, где <tex>i = 1, 2,\ldots, |\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>.}}
Доказательство. Возьмем слово a, которое допускает автомат < tex> A_1</tex> и автомат <tex> A_2 </tex>. Выпишем все состояния в порядке допуска слова a автоматом <tex>A_1</tex> {{---}} <tex> a_{11}, a_{12}, ... , a_{1|a|} </tex> и все состояния проходимыме при допуске слова автоматом <tex>A_2</tex> {{---}} <tex> a_{21}, a_{22}, ... , a_{2|a|} </tex>.
== Применение ==
Изменив конструкцию, можно получить автомат, допускающий разность или объединение двух языков.
[[Файл:Multi_DKA_united.png]]
Необходимо разрешать любую цепочку, удовлетворяющую первому или второму автомату, для . Для этого сделаем терминальными следующие вершины <tex>T = (T_1 \times Q_2) \cup (Q_1 \times T_2)</tex>. Полученный автомат удовлетворяет нашим требованиям, так как попав в какое-либо состояние из <tex>T_1</tex> или <tex>T_2</tex>, цепочка будет удовлетворять первому или второму автомату соответственно.
=== Разность ДКА ===
Следовательно, надо построить пересечение двух автоматов, предварительно инвертировав во втором терминальные и нетерминальные состояния. Заметим, что меняется только набор терминальных вершин, следовательно в итоговой конструкции произведения ДКА сделаем терминальными следующие вершины <tex>T = T_1 \times (Q_2 \setminus T_2)</tex>.
 
 
Таким образом получено альтернативное доказательство [[Замкнутость регулярных языков относительно различных операций|замкнутости регулярных языков относительно теоретико-множественных операций]].
== См. также ==
442
правки

Навигация