Прямое произведение ДКА — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 32: Строка 32:
 
#*...
 
#*...
  
 +
Доказательство.  Возьмем слово 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>.
 
== Применение ==
 
== Применение ==
 
Изменив конструкцию, можно получить автомат, допускающий разность или объединение двух языков.
 
Изменив конструкцию, можно получить автомат, допускающий разность или объединение двух языков.

Версия 15:13, 9 октября 2014

Определение:
Прямым произведением двух ДКА [math]A_1 = \langle \Sigma_1, Q_1, s_1, T_1, \delta_1 \rangle[/math] и [math]A_2 = \langle \Sigma_2, Q_2, s_2, T_2, \delta_2 \rangle[/math] называется ДКА [math]A = \langle \Sigma, Q, s, T, \delta \rangle[/math], где:
  • [math]\Sigma = \Sigma_1 \cup \Sigma_2[/math]
  • [math]Q = Q_1 \times Q_2[/math]
  • [math]s = \langle s_1, s_2 \rangle[/math]
  • [math]T = T_1 \times T_2[/math]
  • [math]\delta(\langle q_1, q_2 \rangle, c) = \langle \delta_1(q_1, c), \delta_2(q_2, c) \rangle[/math]


Пример

Multi DKA source.png

Возьмем автоматы:

  • [math]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[/math]
  • [math]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[/math].

Multi DKA result.png

Автомат [math]A = \langle \Sigma, Q, s, T, \delta \rangle[/math] будет их пересечением.

Согласно определению:

  1. [math]\Sigma = \lbrace 0, 1 \rbrace[/math]
  2. [math]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[/math]
  3. [math]s = \langle s_1, s_2 \rangle[/math]
  4. [math]T = \lbrace \langle t_1, t_{21} \rangle, \langle t_1, t_{22} \rangle \rbrace[/math]
  5. [math]\delta :[/math]
    • [math]\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 [/math]
    • [math]\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 [/math]
    • [math]\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 [/math]
    • [math]\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 [/math]
    • ...

Доказательство. Возьмем слово a, которое допускает автомат < tex> A_1</tex> и автомат [math] A_2 [/math]. Выпишем все состояния в порядке допуска слова a автоматом [math]A_1[/math][math] a_{11}, a_{12}, ... , a_{1|a|} [/math] и все состояния проходимыме при допуске слова автоматом [math]A_2[/math][math] a_{21}, a_{22}, ... , a_{2|a|} [/math].

Применение

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

Объединение ДКА

Multi DKA united.png

Необходимо разрешать любую цепочку, удовлетворяющую первому или второму автомату, для этого сделаем терминальными следующие вершины [math]T = (T_1 \times Q_2) \cup (Q_1 \times T_2)[/math]. Полученный автомат удовлетворяет нашим требованиям, так как попав в какое-либо состояние из [math]T_1[/math] или [math]T_2[/math], цепочка будет удовлетворять первому или второму автомату соответственно.

Разность ДКА

Multi DKA division.png

Рассмотрим автомат [math]\overline{M} = \langle \Sigma , Q , s , Q \setminus T , \delta \rangle [/math], то есть автомат [math]M[/math], в котором терминальные и нетерминальные состояния инвертированы, если в автомате было опущено «дьявольское состояние», его необходимо добавить и сделать терминальным. Очевидно, он допускает те и только те слова, которые не допускает автомат [math]M[/math], а значит, задаёт язык [math]\overline{M}[/math].

Заметим, что если [math]L[/math] и [math]M[/math] — регулярные языки, то [math]L \setminus M = L \cap \overline{M}[/math] — так же регулярный.

Следовательно, надо построить пересечение двух автоматов, предварительно инвертировав во втором терминальные и нетерминальные состояния. Заметим, что меняется только набор терминальных вершин, следовательно в итоговой конструкции произведения ДКА сделаем терминальными следующие вершины [math]T = T_1 \times (Q_2 \setminus T_2)[/math].

См. также

Источники информации