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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Пример)
м (Пример)
Строка 10: Строка 10:
 
== Пример ==
 
== Пример ==
 
[[Файл:Multi_DKA_source.png]]
 
[[Файл: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>
+
 
 +
Возьмем автомат <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]]
 
[[Файл:Multi_DKA_result.png]]
 +
 
Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex> будет их пересечением.
 
Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex> будет их пересечением.
  

Версия 22:31, 8 октября 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](0)^*1[/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] допускающий слова [math](01)^*[/math].

Multi DKA result.png

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

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

  • [math]\Sigma = \lbrace 0, 1 \rbrace[/math]
  • [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]
  • [math]s = \langle s_1, s_2 \rangle[/math]
  • [math]T = \lbrace \langle t_1, t_{21} \rangle, \langle t_1, t_{22} \rangle \rbrace[/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, q_2 \rangle, 1) = \langle \delta_1(s_1, 1), \delta_2(q_2, 1) \rangle = \langle t_1, t_{21} \rangle [/math]

Действительно, заметим, что только слово [math]01[/math] допускается автоматом [math]A_1[/math] и [math]A_2[/math] одновременно.

Применение