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

Определение:

Прямым произведением двух ДКА [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]

Пример

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

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

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

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]

Применение

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

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

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

Разность ДКА

Рассмотрим автомат [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].

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

См. также

• Детерминированные конечные автоматы
• Замкнутость регулярных языков относительно различных операций

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

• Wikipedia — Deterministic finite automaton
• Lecture "Formal languages, automata and computation" : Carnegie Mellon University in Qatar
• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 152-154.