418
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Двусторонний детерминированный конечный автомат (2ДКА)''' (англ. ''Two-way deterministic finite automaton (2DFA)'') {{---}} набор из восьми элементов <tex>M = \langle \Sigma , Q, L, R, s, t, r, \delta \rangle</tex>, где * <tex>\Sigma</tex> {{---}} алфавит (англ. ''alphabet''), * <tex>Q</tex> {{---}} множество состояний (англ. ''finite set of states''), * <tex>L \notin \Sigma</tex> {{---}} левый маркер конца строки (англ. ''left endmarker''), * <tex>R \notin \Sigma</tex> {{---}} правый маркер конца строки (англ. ''right endmarker''), * <tex>s \in Q</tex> — начальное (стартовое) состояние (англ. ''start state''), * <tex>t \in Q</tex> {{---}} допускающее состояние (англ. ''accept state''), * <tex>r \in Q</tex> — отвергающее состояние (англ. ''reject state''), * <tex>\delta : Q \times \{\Sigma \cup \{L, R\}\} \to Q \times \{left, right\}</tex> {{---}} функция переходов (англ. ''transition function'').
}}
Также должны быть удовлетворены следующие условия:
== Регулярность языка ==
{{Теорема
|statement=Классы языков ДКА и 2ДКА совпадают.
|proof=
Рассмотрим длинную входную строку <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>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> {{---}} регулярный язык, что согласно теореме Клини, совпадает с классом и автоматных языков, ч.т.д.}}
== Пример ==
== См. также ==
* [[Детерминированные конечные автоматы]]
* [[Локальные автоматы]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
== Источники информации==
* [[wikipedia:Two-way_deterministic_finite_automaton|Wikipedia {{---}} Two-way deterministic finite automaton]]
* [[wikipedia:ru:Теорема_Майхилла_—_Нероуда|Википедия {{---}} Теорема Майхилла-Нероуда]]
* [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'']
