Редактирование: Двусторонний детерминированный конечный автомат

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 28: Строка 28:
 
Рассмотрим длинную входную строку <tex>w_1</tex> и разобьем на две подстроки <tex>w_1=xz</tex>. Будем считать, что <tex>w_1 = a_1 a_2 a_3 \dots a_n</tex>. Пусть <tex>a_0 = L</tex> и <tex>a_{n+1}=R</tex>. Так как у нас наш автомат может производить чтение в любом направлении, то граница <tex>x</tex> и <tex>z</tex> может быть пересечена несколько раз. Каждый раз, когда автомат пересекает границу справа налево (то есть из <tex>z</tex> в <tex>x</tex>), он выходит из <tex>z</tex> в состояние <tex>q</tex>. Когда пересечение происходит снова слева направо (если оно вообще происходит), то автомат выходит из <tex>x</tex> в состояние <tex>p</tex>. Теперь, если 2ДКА перейдет в <tex>x</tex> в состояние <tex>q</tex> заново, то он снова может появиться в состоянии <tex>p</tex>. Более того, состояние <tex>p</tex> зависит исключительно от <tex>q</tex> и <tex>x</tex>. Обозначим такое отношение через <tex>T_x(q) = p</tex>. Мы может записать все такие отношения в виде конечной таблицы <tex>T_x : Q \cup \{d\} \to Q \cup \{h\}</tex>, где <tex>Q</tex> {{---}} множество состояний 2ДКА, а <tex>d</tex> и <tex>h</tex> будут описаны ниже.
 
Рассмотрим длинную входную строку <tex>w_1</tex> и разобьем на две подстроки <tex>w_1=xz</tex>. Будем считать, что <tex>w_1 = a_1 a_2 a_3 \dots a_n</tex>. Пусть <tex>a_0 = L</tex> и <tex>a_{n+1}=R</tex>. Так как у нас наш автомат может производить чтение в любом направлении, то граница <tex>x</tex> и <tex>z</tex> может быть пересечена несколько раз. Каждый раз, когда автомат пересекает границу справа налево (то есть из <tex>z</tex> в <tex>x</tex>), он выходит из <tex>z</tex> в состояние <tex>q</tex>. Когда пересечение происходит снова слева направо (если оно вообще происходит), то автомат выходит из <tex>x</tex> в состояние <tex>p</tex>. Теперь, если 2ДКА перейдет в <tex>x</tex> в состояние <tex>q</tex> заново, то он снова может появиться в состоянии <tex>p</tex>. Более того, состояние <tex>p</tex> зависит исключительно от <tex>q</tex> и <tex>x</tex>. Обозначим такое отношение через <tex>T_x(q) = p</tex>. Мы может записать все такие отношения в виде конечной таблицы <tex>T_x : Q \cup \{d\} \to Q \cup \{h\}</tex>, где <tex>Q</tex> {{---}} множество состояний 2ДКА, а <tex>d</tex> и <tex>h</tex> будут описаны ниже.
  
На входной строке <tex>xz</tex> 2ДКА начнет чтение с левого маркера конца строки. В процессе работы автомата позиция чтения будет меняться. В конце концов это позиция пересечет слева направо границу между <tex>x</tex> и <tex>z</tex>. В первый раз это произойдет в каком-нибудь состоянии, которое будем называть <tex>T_x(d)</tex> (для этого мы и выделили <tex>d</tex>). Так же автомат может никогда не выйти из <tex>x</tex>. В таком случае мы запишем <tex>T_x(d) = h</tex>. Состояние <tex>T_x(d)</tex> дает немного информации о <tex>x</tex>, но только конечное количество, поскольку существует только конечное количество вариантов для <tex>T_x(d)</tex>. Отметим, что <tex>T_x(d)</tex> зависит только от <tex>x</tex> и не зависит от <tex>z</tex>. Если на вход подавалась бы строка <tex>xw</tex> вместо <tex>xz</tex>, то в таком случае при пересечении границы из <tex>x</tex> в <tex>w</tex> автомат также был бы в состоянии <tex>T_x(d)</tex>, потому что его значение до того момента определялось только <tex>x</tex> и до тех пор все, что находится справа от границы никак не влияет.
+
На входной строке <tex>xz</tex> 2ДКА начнет чтение с левого маркера конца строки. В процессе работы автомата позиция чтения будет меняться. В конце концов это позиция пересечет слева направо границу между <tex>x</tex> и <tex>z</tex>. В первый раз это произойдет в каком-нибудь состоянии, которое будем называть <tex>T_x(d)</tex> (для этого мы и выделили <tex>d</tex>). Так же автомат может никогда не выйти из <tex>x</tex>. В таком случае мы запишем <tex>T_x(d) = h</tex>. Состояние <tex>T_x(d)</tex> дает немного информации о <tex>x</tex>, но только конечное количество, поскольку существует только конечное количество вариантов для <tex>T_x(d)</tex>. Отметим, что <tex>T_x(d)</tex> зависит только от <tex>x</tex> и не зависит от <tex>z</tex>. Если на вход подавалась строка <tex>xw</tex> вместо <tex>xz</tex>, то в таком случае при пересечении границы из <tex>x</tex> в <tex>w</tex> автомат также был бы в состоянии <tex>T_x(d)</tex>, потому что его значение до того момента определялось только <tex>x</tex> и до тех пор все, что находится справа от границы никак не влияет.
  
 
Если <tex>T_x(d) = h</tex>, то 2ДКА в бесконечном цикле внутри <tex>x</tex>, и он никогда не допустит и не отвергнет входную строку.
 
Если <tex>T_x(d) = h</tex>, то 2ДКА в бесконечном цикле внутри <tex>x</tex>, и он никогда не допустит и не отвергнет входную строку.
  
Предположим, что 2ДКА переходит из <tex>x</tex> в <tex>z</tex> и спустя время переходит обратно в состояние <tex>q</tex>. Если это происходит, то потом:
+
Предположим, что 2ДКА переходит из <tex>x</tex> в <tex>z</tex> и спустя время перейти обратно в состояние <tex>q</tex>. Если это происходит, то потом:
 
* либо снова произойдет переход из <tex>x</tex> в некоторое состояние <tex>p</tex>. В таком случае мы определим <tex>T_x(q)=p</tex>.
 
* либо снова произойдет переход из <tex>x</tex> в некоторое состояние <tex>p</tex>. В таком случае мы определим <tex>T_x(q)=p</tex>.
 
* либо никогда не перейдет. В таком случае <tex>T_x(q) = h</tex>.
 
* либо никогда не перейдет. В таком случае <tex>T_x(q) = h</tex>.

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

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

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

Шаблоны, используемые на этой странице: