Редактирование: Прямое произведение ДКА

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Прямым произведением''' двух [[Детерминированные конечные автоматы|ДКА]] <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>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>\Sigma = \Sigma_1 \cup \Sigma_2</tex>
+
* <tex>Q = Q_1 \times Q_2,</tex>
* <tex>Q = Q_1 \times Q_2</tex>
+
* <tex>s = \langle s_1, s_2 \rangle,</tex>
* <tex>s = \langle s_1, s_2 \rangle</tex>
+
* <tex>T = T_1 \times T_2,</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>
* <tex>\delta(\langle q_1, q_2 \rangle, c) = \langle \delta_1(q_1, c), \delta_2(q_2, c) \rangle</tex>
 
 
}}
 
}}
  
Строка 12: Строка 11:
 
[[Файл: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>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>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]]
Строка 53: Строка 50:
 
[[Файл:Multi_DKA_division.png]]
 
[[Файл: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>\overline{M} = \langle \Sigma , Q , s , Q \setminus T , \delta \rangle </tex>, то есть автомат <tex>M</tex>, в котором терминальные и нетерминальные состояния инвертированы. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>M</tex>, а значит, задаёт язык <tex>\overline{M}</tex>. Таким образом, <tex>\overline{M}</tex> {{---}} регулярный.
  
Заметим, что если <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то <tex>L \setminus M = L \cap \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>.
+
Таким образом, надо построить пересечение двух автоматов, предварительно инвертировав во втором терминальные и нетерминальные состояния. Заметим, что меняется только набор терминальных вершин, следовательно в итоговой конструкции произведения ДКА сделаем терминальными следующие вершины <tex>T = T_1 \times (Q_2 \setminus T_2)</tex>.
  
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)