Изменения

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

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

1097 байт добавлено, 02:02, 10 января 2015
Нет описания правки
* <tex>\delta(t, R) = (t, left)</tex>,
* <tex>\delta(r, R) = (r, left)</tex>.
== Описание ==
Зафиксируем <tex>x \in \Sigma^*</tex>, где <tex>x = a_1 a_2 a_3 \dots a_n</tex>. Пусть <tex>a_0 = L</tex> и <tex>a_{n+1}=R</tex>. Тогда <tex>a_0 a_1 a_2 \dots a_n a_{n+1} = L x R</tex>.
== Регулярность языка ==Рассмотрим длинную входную строку <tex>w_1</tex> и разобьем на две подстроки <tex>w_1=xz</tex>. Будем считать, что <tex>w_1 = a_1 a_2 a_3 \dots a_n</tex>. Пусть дан 2ДКА <tex>A a_0 = \langle \Sigma , Q, L, </tex> и <tex>a_{n+1}=R</tex>. Так как у нас наш автомат может производить чтение в любом направлении, sто граница <tex>x</tex> и <tex>z</tex> может быть пересечена несколько раз. Каждый раз, tкогда автомат пересекает границу справа налево (то есть из <tex>z</tex> в <tex>x</tex>), rон выходит из <tex>z</tex> в состояние <tex>q</tex>. Когда пересечение происходит снова слева направо (если оно вообще происходит), \delta \rangleто автомат выходит из <tex>x</tex> с в состояние <tex>np</tex> состояниями. Тогда можно построить ДКАТеперь, распознающий язык тот же языкесли 2ДКА перейдет в <tex>x</tex> в состояние <tex>q</tex> заново, с то он снова может появиться в состоянии <tex>p</tex>. Более того, состояние <tex>p</tex> зависит исключительно от <tex>q</tex> и <tex>x</tex>O. Обозначим такое отношение через <tex>T_x(e^nq)= 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>B x</tex> и <tex>z</tex>. В первый раз, когда это произойдет в каком-нибудь состоянии <tex>T_x(d)</tex> (для этого мы и выделили <tex>d</tex>). Так же автомат может никогда не выйти из <tex>x</tex>. В таком случае мы запишем <tex>T_x(d) = \langle \Sigma h</tex>. Состояние <tex>T_x(d)</tex> дает немного информации о <tex>x</tex>, Qно только конечное количество, s \in Qпоскольку существует только конечное количество вариантов для <tex>T_x(d)</tex>. Отметим, что <tex>T_x(d)</tex> зависит только от <tex>x</tex> и не зависит от <tex>z</tex>. Если на вход подавалась строка <tex>xw</tex> вместо <tex>xz</tex>, T \subset Qто в таком случае при пересечении границы из <tex>x</tex> в <tex>w</tex> автомат также был бы в состоянии <tex>T_x(d)</tex>, \delta : Q \times \Sigma \to Q \rangleпотому что его значение до того момента определялось только <tex>x</tex>и до тех пор все, что находится справа от границы никак не влияет.
== Регулярность языков ==Рассмотрим длинную входную строку <tex>w_1</tex> и разобьем на две подстроки <tex>w_1=xz</tex>. Так как у нас наш автомат может производить чтение в любом направлении, то граница <tex>x</tex> и <tex>z</tex> может быть пересечена несколько раз. Каждый раз, когда автомат пересекает границу справа налево (то есть из <tex>z</tex> в <tex>x</tex>), он выходит из состояния <tex>q</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>T_x(d) = h</tex>, то 2ДКА должен быть в бесконечном цикле внутри <tex>x</tex> , и он никогда не допустит или и не отвергнет входную строку.
Предположим, что 2ДКА переходит из <tex>x</tex> в <tex>z</tex> и спустя время перейти обратно в состояние <tex>q</tex>. Если это происходит, то потом:
* либо никогда не перейдет. В таком случае <tex>T_x(q) = h</tex>.
Ещё раз отметим, что <tex>T_x(q)</tex> зависит только от <tex>x</tex> и <tex>q</tex> и не зависит от <tex>z</tex>. Если автомат переходит в <tex>x</tex> справа в состояние <tex>q</tex>, то тогда он появится заново в состоянии <tex>T_x(q)</tex> (или никогда не перейдет, если <tex>T_x(q) = h</tex>), потому что автомат детерминированный, и поведение его поведение полностью определяется <tex>x</tex> и состоянием, в которое он вошел.
Если мы запишем <tex>T_x(q)</tex> для каждого состояния <tex>q</tex> вместе с <tex>T_x(d)</tex>, это даст нам всю информацию о <tex>x</tex>, которую можно перенести через границу между <tex>x</tex> и <tex>z</tex>. Все это позволит узнать <tex>T_x(d)</tex> сразу после пересечения границы, а также посмотреть значения <tex>T_x(q)</tex>. Если <tex>y</tex> {{---}} другая строка, такая что <tex>T_y=T_x</tex>, то тогда <tex>x</tex> и <tex>y</tex> будут неразличимы.
Теперь мы может использовать теорему Майхилла-Нероуда, чтобы показать, что язык <tex>L(M)</tex> нашего автомата <tex>M</tex> [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярный]].
<tex>T_x = T_y \Rightarrow \forall z (M\ \text{accepts}\ xz \Leftrightarrow M\ \text{accepts}\ yz)</tex> <tex> \Leftrightarrow \forall z (xz \in L(M)</tex> <tex> \Leftrightarrow yz \in L(M)) \Leftrightarrow x \equiv_{L(M)} y</tex>, где <tex>\equiv_{L(M)}</tex> {{---}} [[Отношение_эквивалентности|отношение эквивалентности]] на множестве слов в алфавите. Таким образом, если 2 строки имеют одинаковые таблицы, то тогда они эквивалентны отношением <tex>\equiv_{L(M)}</tex>. Поскольку у нас только конечное число таблиц, отношение <tex>\equiv_{L(M)}</tex> имеет только конечное количество [[Отношение_эквивалентности|классов эквивалентности]], самое большее один для каждой таблицы. По теореме <tex>L(M)</tex> {{---}} регулярный язык, ч.т.д.
== Пример ==
Он может быть легко распознан с помощью следующего недетерменированного конечного автомата.
 
[[Файл:2dfa_example_1.png|600px]]
Теперь построим на его основе ДКА. Мы можем построить автомат <tex>A_n</tex>, который запоминает последние <tex>n</tex> входных символов. Следовательно, когда мы находимся с состоянии, соответствующему подстроке <tex>\sigma_1 \sigma_2 \dots \sigma_n</tex>, и читаем очередной символ <tex>\gamma</tex>, то мы переходим в состояние, которому уже будет соответствовать подстрока <tex>\sigma_2 \sigma_3 \dots \sigma_n \gamma</tex>. Однако, в случае <tex>\sigma_1 = \gamma = a</tex> автомат переходит в допускающее состояние, где в цикле может переходить на любому символу. Следует отметить, что такая стратегия строит ДКА c <tex>2^n + 1</tex> состояниями. Ниже представлен автомат <tex>A_3</tex>, который распознает язык <tex>L_3</tex>.
 
[[Файл:2dfa_example_2.png|500px]]
Покажем, что построенные таким образом автоматы будут минимальными.
* Каждая строка длины <tex>n</tex> не принадлежит <tex>L_n</tex> и, следовательно, различима от строки <tex>a^{n+1}</tex>, которая принадлежит <tex>L_n</tex>.
* Таким образом, <tex>2^n + 1</tex> строк в <tex>\Sigma^n \cup \{a^{n+1}\}</tex> являются попарно различимыми для <tex>L_n</tex>. Как следствие, <tex>2^n + 1</tex> {{---}} минимальное количество состояний для ДКА, который способен распознать язык <tex>L_n</tex>.
 
Чтобы определить, что строка <tex>w=c_1 \dots c_n</tex> принадлежит языку <tex>L_n</tex>, нужно для <tex>\forall i = 1, \dots, |w|-n</tex> проверить, что <tex>c_i=c_{i+n}=a</tex>. Строка будет допустимой, если условие сработает хотя бы для одного <tex>i</tex>. Этот алгоритм может быть просто реализован с помощью 2ДКА. Будем для каждого <tex>i</tex> двигаться на <tex>n</tex> позиций вперед, а потом на <tex>n-1</tex> позиций назад до позиции <tex>i+1</tex>. Кроме того, при движении с позиции <tex>i</tex> до <tex>i+n</tex> автомат должен помнить сохраняется ли условие <tex>c_i=a</tex>. Такой подход требует <tex>O(n)</tex> состояний.
== См. также ==
* [[wikipedia:ru:Теорема_Майхилла_—_Нероуда|Википедия {{---}} Теорема Майхилла-Нероуда]]
* [[Детерминированные конечные автоматы]]
== Источники информации==
* [[wikipedia:Two-way_deterministic_finite_automaton|Wikipedia {{---}} Two-way deterministic finite automaton]]* [http://arxiv.org/pdf/1208.2755.pdf Giovanni Pighizzini, ''Two-Way Finite Automata: Old and Recent Results'']* [http://www.cs.cornell.edu/Courses/cs682/2008sp/Handouts/2DFA.pdf Cornell University, ''Two-Way Finite Automata'']* [http://webcourse.cs.technion.ac.il/236807/Spring2012/ho/WCFiles/Two-way%20finite%20automata%20new.pdf Liat Peterfreund, ''Two-way finite automata & pebble automata'']
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
418
правок

Навигация