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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 28: Строка 28:
 
#*<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, 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>\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> будет их пересечением.
 
|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>, так как:
+
|proof=Возьмем слово <tex>\alpha</tex>, которое допускает автомат <tex>A_1</tex> и автомат <tex>A_2</tex>. Выпишем все состояния в порядке допуска слова <tex>\alpha</tex> автоматом <tex>A_1</tex> {{---}} <tex>a_{11}, a_{12}, ... , a_{1|\alpha|}</tex> и все состояния проходимые при допуске слова автоматом <tex>A_2</tex> {{---}} <tex>a_{21}, a_{22}, ... , a_{2|\alpha|}</tex>. Построим список пар <tex>\langle a_{1i}, a_{2i} \rangle</tex>,  где <tex>i = 1, 2, ..., |\alpha|</tex>. Данный список является списком состояний в процессе допуска слова <tex>\alpha</tex> автоматом <tex>A</tex>, так как:
  
 
*<tex>\langle a_{11}, a_{21} \rangle = \langle s_1, s_2 \rangle</tex> {{---}} сохраняется стартовое состояние
 
*<tex>\langle a_{11}, a_{21} \rangle = \langle s_1, s_2 \rangle</tex> {{---}} сохраняется стартовое состояние

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

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

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