Изменения

Перейти к: навигация, поиск

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

5437 байт добавлено, 20:50, 10 марта 2018
Нет описания правки
{{Определение
|definition=
'''Прямым произведением''' двух [[Детерминированные конечные автоматы|ДКА]] <tex>A_1 = \langle \SigmaSigma_1, Q_1, s_1, T_1, \delta_1 \rangle</tex> и <tex>A_2 = \langle \SigmaSigma_2, Q_2, s_2, T_2, \delta_2 \rangle</tex> называется ДКА <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex>, где:* <tex>\Sigma = \Sigma_1 \cup \Sigma_2</tex>* <tex>Q = Q_1 \times Q_2,</tex>* <tex>s = \langle s_1, s_2 \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>
}}
[[Файл: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>.
[[Файл:Multi_DKA_result.png]]
Согласно определению:#<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>\Sigma = \lbrace 0, a_{1 |\rbrace</tex>*<tex>Q = \lbrace alpha|} \langle s_1in T_1, s_2 a_{2|\rangle, alpha|} \langle s_1, q_2 \ranglein T_2, \langle s_1, t_a_{211|\alpha|} \rangle, \langle s_1, t_a_{22} 2|\rangle, \langle t_1, s_2 \rangle, \langle t_1, q_2 \rangle, \langle t_1, t_{21alpha|} \rangle, \langle t_1, t_{21} in T_1 \rangle \rbrace</tex>*<tex>s times T_2 = \langle s_1, s_2 \rangleT</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 A</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 A_1</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 A_2</tex>.
Действительно, заметим, что только Возьмем слово <tex>01\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. [[Категория: Теория формальных языков]].[[Категория: Автоматы и регулярные языки]]
442
правки

Навигация