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

Материал из Викиконспекты
Версия от 20:50, 10 марта 2018; Ponomarev (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Прямым произведением двух ДКА [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

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

  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]
    • [math]\ldots[/math]
Утверждение:
Автомат [math]A = \langle \Sigma, Q, s, T, \delta \rangle[/math], построенный как прямое произведение автоматов [math]A_1[/math] и [math]A_2[/math] будет их пересечением.
[math]\triangleright[/math]

Возьмем слово [math]\alpha[/math], которое допускает автомат [math]A_1[/math] и автомат [math]A_2[/math]. Выпишем все состояния в порядке допуска слова [math]\alpha[/math] автоматом [math]A_1[/math][math]a_{11}, a_{12},\ldots, a_{1|\alpha|}[/math] и все состояния проходимые при допуске слова автоматом [math]A_2[/math][math]a_{21}, a_{22},\ldots, a_{2|\alpha|}[/math]. Построим список пар [math]\langle a_{1i}, a_{2i} \rangle[/math], где [math]i = 1, 2,\ldots, |\alpha|[/math]. Данный список является списком состояний в процессе допуска слова [math]\alpha[/math] автоматом [math]A[/math], так как:

  • [math]\langle a_{11}, a_{21} \rangle = \langle s_1, s_2 \rangle[/math] — сохраняется стартовое состояние
  • [math]\delta_1(a_{1i-1},c) = a_{1i}[/math], [math]\delta_2(a_{2i-1},c) = a_{2i}[/math], [math]\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[/math] — переходы верны
  • [math]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[/math] — сохраняется терминальное состояние

Следовательно автомат [math]A[/math] допускает слова, которые допускает автомат [math]A_1[/math] и автомат [math]A_2[/math].

Возьмем слово [math]\beta[/math], которое не допускает автомат [math]A_1[/math] или автомат [math]A_2[/math], тогда [math]a_{1|\beta|}[/math] или [math]a_{2|\beta|}[/math] — нетерминальное состояние, следовательно [math]\langle a_{1|\beta|}, a_{2|\beta|} \rangle \notin T_1 \times T_2[/math].
[math]\triangleleft[/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].


Таким образом получено альтернативное доказательство замкнутости регулярных языков относительно теоретико-множественных операций.

См. также[править]

Источники информации[править]