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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Пример)
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Прямым произведением''' двух [[Детерминированные конечные автоматы|ДКА]] <tex>A_1 = \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle</tex> и <tex>A_2 = \langle \Sigma, Q_2, s_2, T_2, \delta_2 \rangle</tex> называется ДКА <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex>, где:
+
'''Прямым произведением''' двух [[Детерминированные конечные автоматы|ДКА]] <tex>A_1 = \langle \Sigma_1, Q_1, s_1, T_1, \delta_1 \rangle</tex> и <tex>A_2 = \langle \Sigma_2, Q_2, s_2, T_2, \delta_2 \rangle</tex> называется ДКА <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex>, где:
* <tex>Q = Q_1 \times Q_2,</tex>
+
* <tex>\Sigma = \Sigma_1 \cup \Sigma_2</tex>
* <tex>s = \langle s_1, s_2 \rangle,</tex>
+
* <tex>Q = Q_1 \times Q_2</tex>
* <tex>T = T_1 \times T_2,</tex>
+
* <tex>s = \langle s_1, s_2 \rangle</tex>
* <tex>\delta(\langle q_1, q_2 \rangle, c) = \langle \delta_1(q_1, c), \delta_2(q_2, c) \rangle.</tex>
+
* <tex>T = T_1 \times T_2</tex>
 +
* <tex>\delta(\langle q_1, q_2 \rangle, c) = \langle \delta_1(q_1, c), \delta_2(q_2, c) \rangle</tex>
 
}}
 
}}
  
Строка 11: Строка 12:
 
[[Файл: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>.
+
Возьмем автоматы:
 +
* <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>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>.
  
 
[[Файл:Multi_DKA_result.png]]
 
[[Файл:Multi_DKA_result.png]]
  
Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</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>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>\delta :</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, 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, 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>\ldots</tex>
 +
{{Утверждение
 +
|statement=Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex>, построенный как прямое произведение автоматов <tex>A_1</tex> и <tex>A_2</tex> будет их пересечением.
 +
|proof=Возьмем слово <tex>\alpha</tex>, которое допускает автомат <tex>A_1</tex> и автомат <tex>A_2</tex>. Выпишем все состояния в порядке допуска слова <tex>\alpha</tex> автоматом <tex>A_1</tex> {{---}} <tex>a_{11}, a_{12},\ldots, a_{1|\alpha|}</tex> и все состояния проходимые при допуске слова автоматом <tex>A_2</tex> {{---}} <tex>a_{21}, a_{22},\ldots, a_{2|\alpha|}</tex>. Построим список пар <tex>\langle a_{1i}, a_{2i} \rangle</tex>,  где <tex>i = 1, 2,\ldots, |\alpha|</tex>. Данный список является списком состояний в процессе допуска слова <tex>\alpha</tex> автоматом <tex>A</tex>, так как:
 +
 
 +
*<tex>\langle a_{11}, a_{21} \rangle = \langle s_1, s_2 \rangle</tex> {{---}} сохраняется стартовое состояние
 +
 
 +
*<tex>\delta_1(a_{1i-1},c) = a_{1i}</tex>, <tex>\delta_2(a_{2i-1},c) = a_{2i}</tex>, <tex>\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</tex> {{---}} переходы верны
  
Согласно определению:
+
*<tex>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</tex> {{---}} сохраняется терминальное состояние
*<tex>\Sigma = \lbrace 0, 1 \rbrace</tex>
+
Следовательно автомат <tex>A</tex> допускает слова, которые допускает автомат <tex>A_1</tex> и автомат <tex>A_2</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>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(\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, t_{21} \rangle, 0) = \langle \delta_1(s_1, 0), \delta_2(t_{21}, 0) \rangle = \langle s_1, q_2 \rangle </tex>
 
  
Действительно, заметим, что только слово <tex>01</tex> допускается автоматом <tex>A_1</tex> и <tex>A_2</tex> одновременно.
+
Возьмем слово <tex>\beta</tex>, которое не допускает автомат <tex>A_1</tex> или автомат <tex>A_2</tex>, тогда <tex>a_{1|\beta|}</tex> или <tex>a_{2|\beta|}</tex> {{---}} нетерминальное состояние, следовательно <tex>\langle a_{1|\beta|}, a_{2|\beta|} \rangle \notin T_1 \times T_2</tex>.
 +
}}
  
 
== Применение ==
 
== Применение ==
* С помощью данной конструкции можно построить автомат для [[Замкнутость регулярных языков относительно различных операций|пересечения]] [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].
+
Изменив конструкцию, можно получить автомат, допускающий разность или объединение двух языков.
 +
=== Объединение ДКА ===
 +
[[Файл:Multi_DKA_united.png]]
 +
 
 +
Необходимо разрешать любую цепочку, удовлетворяющую первому или второму автомату. Для этого сделаем терминальными следующие вершины <tex>T = (T_1 \times Q_2) \cup (Q_1 \times T_2)</tex>. Полученный автомат удовлетворяет нашим требованиям, так как попав в какое-либо состояние из <tex>T_1</tex> или <tex>T_2</tex>, цепочка будет удовлетворять первому или второму автомату соответственно.
 +
 
 +
=== Разность ДКА ===
 +
[[Файл:Multi_DKA_division.png]]
 +
 
 +
Рассмотрим автомат <tex>\overline{M} = \langle \Sigma , Q , s , Q \setminus T , \delta \rangle </tex>, то есть автомат <tex>M</tex>, в котором терминальные и нетерминальные состояния инвертированы, если в автомате было опущено «дьявольское состояние», его необходимо добавить и сделать терминальным. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>M</tex>, а значит, задаёт язык <tex>\overline{M}</tex>.
 +
 
 +
Заметим, что если <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то <tex>L \setminus M = L \cap \overline{M}</tex> {{---}} так же регулярный.
 +
 
 +
Следовательно, надо построить пересечение двух автоматов, предварительно инвертировав во втором терминальные и нетерминальные состояния. Заметим, что меняется только набор терминальных вершин, следовательно в итоговой конструкции произведения ДКА сделаем терминальными следующие вершины <tex>T = T_1 \times (Q_2 \setminus T_2)</tex>.
 +
 
 +
 
 +
Таким образом получено альтернативное доказательство [[Замкнутость регулярных языков относительно различных операций|замкнутости регулярных языков относительно теоретико-множественных операций]].
 +
 
 +
== См. также ==
 +
* [[Детерминированные конечные автоматы]]
 +
* [[Замкнутость регулярных языков относительно различных операций]]
 +
 
 +
== Источники информации ==
 +
* [[wikipedia:Deterministic_finite_automaton | Wikipedia {{---}} Deterministic finite automaton]]
 +
* [http://www.andrew.cmu.edu/user/ko/pdfs/lecture-3.pdf Lecture "Formal languages, automata and computation" : Carnegie Mellon University in Qatar]
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.:Издательский дом «Вильямс», 2002. {{---}} С. 152-154.
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:12, 4 сентября 2022

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


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

См. также

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