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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 18: Строка 18:
  
 
Согласно определению:
 
Согласно определению:
*<tex>\Sigma = \lbrace 0, 1 \rbrace</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>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>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>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 :</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, 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, 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, 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, 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, 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>01</tex> допускается автоматом <tex>A_1</tex> и <tex>A_2</tex> одновременно.
 
  
 
== Применение ==
 
== Применение ==
 
Изменив конструкцию, можно получить автомат допускающий разность или объединение двух языков.
 
Изменив конструкцию, можно получить автомат допускающий разность или объединение двух языков.
 
=== Объединение ДКА ===
 
=== Объединение ДКА ===
 +
[[Файл:Multi_DKA_united.png]]
  
Необходимо разрешать любую цепочку удовлетворяющую первому или второму автомату, для этого пометим терминальными следующие вершины <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>, цепочка начинает удовлетворять первому или второму автомату соответственно.
+
Необходимо разрешать любую цепочку удовлетворяющую первому или второму автомату, для этого пометим терминальными следующие вершины <tex>T = (T_1 \times Q_2) \cup (Q_1 \times T_2)</tex>. Полученный автомат удовлетворяет нашим требованиям так как попав в какое-либо состояние из <tex>T_1</tex> или <tex>T_2</tex>, цепочка начинает удовлетворять первому или второму автомату соответственно.
  
 
=== Разность ДКА ===
 
=== Разность ДКА ===

Версия 00:19, 9 октября 2014

Определение:
Прямым произведением двух ДКА [math]A_1 = \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle[/math] и [math]A_2 = \langle \Sigma, Q_2, s_2, T_2, \delta_2 \rangle[/math] называется ДКА [math]A = \langle \Sigma, Q, s, T, \delta \rangle[/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]
    • ...

Применение

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

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

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], цепочка начинает удовлетворять первому или второму автомату соответственно.

Разность ДКА