Двусторонний детерминированный конечный автомат — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Двусторонний детерминированный конечный автомат (2ДКА)''' (англ. ''Two-way deterministic finite automaton (2DFA)'') {{---}} набор из восьми элементов <tex>\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> {{---}} левый маркер конца строки, <tex>R \notin \Sigma</tex> {{---}} правый маркер конца строки, <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'').
+
'''Двусторонний детерминированный конечный автомат (2ДКА)''' (англ. ''Two-way deterministic finite automaton (2DFA)'') {{---}} набор из восьми элементов <tex>M = \langle \Sigma , Q, L, R, s, t, r, \delta \rangle</tex>, где
 +
* <tex>\Sigma</tex> {{---}} алфавит,
 +
* <tex>Q</tex> {{---}} множество состояний,
 +
* <tex>L \notin \Sigma</tex> {{---}} левый маркер конца строки (англ. ''left endmarker''),
 +
* <tex>R \notin \Sigma</tex> {{---}} правый маркер конца строки (англ. ''right endmarker''),
 +
* <tex>s \in Q</tex> — начальное (стартовое) состояние,
 +
* <tex>t \in Q</tex> {{---}} допускающее состояние,
 +
* <tex>r \in Q</tex> — отвергающее состояние,
 +
* <tex>\delta : Q \times \{\Sigma \cup \{L, R\}\} \to Q \times \{left, right\}</tex> {{---}} функция переходов.
 
}}
 
}}
 
Также должны быть удовлетворены следующие условия:
 
Также должны быть удовлетворены следующие условия:
Строка 13: Строка 21:
 
* <tex>\delta(t, R) = (t, left)</tex>,
 
* <tex>\delta(t, R) = (t, left)</tex>,
 
* <tex>\delta(r, R) = (r, 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>.
 
  
Пусть дан 2ДКА <tex>A = \langle \Sigma , Q, L, R, s, t, r, \delta \rangle</tex> с <tex>n</tex> состояниями. Тогда можно построить ДКА, распознающий язык тот же язык, с <tex>O(e^n)</tex> состояниями.
+
== Регулярность языка ==
 +
{{Теорема
 +
|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>B = \langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</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>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> и до тех пор не все, что находится справа от границы никак не влияет.
+
Предположим, что 2ДКА переходит из <tex>x</tex> в <tex>z</tex> и спустя время переходит обратно в состояние <tex>q</tex>. Если это происходит, то потом:
 +
* либо снова произойдет переход из <tex>x</tex> в некоторое состояние <tex>p</tex>. В таком случае мы определим <tex>T_x(q)=p</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>T_x(d) = h</tex>, то 2ДКА должен быть в бесконечном цикле внутри <tex>x</tex> и никогда не допустит или отвергнет входную строку.
+
Заметим, что у нас конечное число возможных таблиц
 +
<tex>T_x : Q \cup \{d\} \to Q \cup \{h\}</tex>,
 +
а именно <tex>(k+1)^{k+1}</tex>, где <tex>k</tex> {{---}} размер множества <tex>Q</tex>. Таким образом, у нас конечное количество информации о <tex>x</tex>, которое мы может перенести через границу справа от <tex>x</tex>, и которое закодировано у нас в таблицe <tex>T_x</tex>.
  
Предположим, что 2ДКА переходит из <tex>x</tex> в <tex>z</tex> и спустя время перейти обратно в состояние <tex>q</tex>. Если это происходит, то потом:
+
Отметим также, что если <tex>T_x=T_y</tex> и автомат допускает строку <tex>xz</tex>, то тогда он допускает и строку <tex>yz</tex>, потому что последовательность состояний, перенесенных через границу <tex>x</tex> и <tex>z</tex> (либо <tex>y</tex> и <tex>z</tex>) в любом направлении, полностью определяется таблицами <tex>T_x=T_y</tex> и строкой <tex>z</tex>. Чтобы допустить строку <tex>xz</tex>, автомат должен в какой-то момент прочитать правый маркер конца строки, находясь в допускающем состоянии <tex>t</tex>.
* либо снова произойдет переход из <tex>x</tex> в некоторое состояние <tex>p</tex>. В таком случае мы определим <tex>T_x(q)=p</tex>.
+
 
* либо никогда не перейдет. В таком случае <tex>T_x(q) = h</tex>.
+
Теперь мы может использовать теорему Майхилла-Нероуда, чтобы показать, что язык <tex>L(M)</tex> нашего автомата <tex>M</tex> [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярный]].
  
Ещё раз отметим, что <tex>T_x(q)</tex> зависит только от <tex>x</tex> и <tex>q</tex> и не зависит от <tex>z</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> {{---}} регулярный язык, что согласно теореме Клини, совпадает с классом и автоматных языков, ч.т.д.
 +
}}
  
 
== Пример ==
 
== Пример ==
 
Рассмотрим следующий язык <tex>L_n = (a+b)^∗a(a+b)^{n-1}a(a+b)^∗</tex> при <tex>\forall n > 0</tex>.
 
Рассмотрим следующий язык <tex>L_n = (a+b)^∗a(a+b)^{n-1}a(a+b)^∗</tex> при <tex>\forall n > 0</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>.
  
Теперь построим на его основе ДКА. Мы можем построить автомат <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>x</tex> и <tex>y</tex> длины <tex>n</tex> различимы. Чтобы доказать это, достаточно рассмотреть строку <tex>b^{i-1}a</tex>, где <tex>i : 1 \leqslant i \leqslant n</tex> {{---}} самая левая позиция символа, в которой начинают различаться строки <tex>x</tex> и <tex>y</tex>, и проверить, что ровно одна строка <tex>xb^{i-1}a</tex> или <tex>yb^{i-1}a</tex> принадлежит <tex>L_n</tex>.
 
* Каждые две попарно различных строки <tex>x</tex> и <tex>y</tex> длины <tex>n</tex> различимы. Чтобы доказать это, достаточно рассмотреть строку <tex>b^{i-1}a</tex>, где <tex>i : 1 \leqslant i \leqslant n</tex> {{---}} самая левая позиция символа, в которой начинают различаться строки <tex>x</tex> и <tex>y</tex>, и проверить, что ровно одна строка <tex>xb^{i-1}a</tex> или <tex>yb^{i-1}a</tex> принадлежит <tex>L_n</tex>.
* Каждая строка длины <tex>n</tex> не принадлежит <tex>L_n</tex> и, следовательно, различима от строки <tex>a^{n+1}</tex>, которая принадлежит <tex>L_n</tex>.
+
* Каждая строка длины <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>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: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'']
 +
* [http://webcourse.cs.technion.ac.il/236807/Spring2012/ho/WCFiles/Two-way%20finite%20automata%20new.pdf Liat Peterfreund, ''Two-way finite automata & pebble automata'']
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Другие автоматы]]

Текущая версия на 19:38, 4 сентября 2022

Определение:
Двусторонний детерминированный конечный автомат (2ДКА) (англ. Two-way deterministic finite automaton (2DFA)) — набор из восьми элементов [math]M = \langle \Sigma , Q, L, R, s, t, r, \delta \rangle[/math], где
  • [math]\Sigma[/math] — алфавит,
  • [math]Q[/math] — множество состояний,
  • [math]L \notin \Sigma[/math] — левый маркер конца строки (англ. left endmarker),
  • [math]R \notin \Sigma[/math] — правый маркер конца строки (англ. right endmarker),
  • [math]s \in Q[/math] — начальное (стартовое) состояние,
  • [math]t \in Q[/math] — допускающее состояние,
  • [math]r \in Q[/math] — отвергающее состояние,
  • [math]\delta : Q \times \{\Sigma \cup \{L, R\}\} \to Q \times \{left, right\}[/math] — функция переходов.

Также должны быть удовлетворены следующие условия:

[math]\forall q \in Q[/math]

  • [math]\delta(q, L) = (u, right)[/math] для некоторого [math]u \in Q[/math],
  • [math]\delta(q, R) = (v, left)[/math] для некоторого [math]v \in Q[/math],

и [math]\forall b \in \Sigma \cup \{L\}[/math]

  • [math]\delta(t, b) = (t, right)[/math],
  • [math]\delta(r, b) = (r, right)[/math],
  • [math]\delta(t, R) = (t, left)[/math],
  • [math]\delta(r, R) = (r, left)[/math].

Регулярность языка

Теорема:
Классы языков ДКА и 2ДКА совпадают.
Доказательство:
[math]\triangleright[/math]

Рассмотрим длинную входную строку [math]w_1[/math] и разобьем на две подстроки [math]w_1=xz[/math]. Будем считать, что [math]w_1 = a_1 a_2 a_3 \dots a_n[/math]. Пусть [math]a_0 = L[/math] и [math]a_{n+1}=R[/math]. Так как у нас наш автомат может производить чтение в любом направлении, то граница [math]x[/math] и [math]z[/math] может быть пересечена несколько раз. Каждый раз, когда автомат пересекает границу справа налево (то есть из [math]z[/math] в [math]x[/math]), он выходит из [math]z[/math] в состояние [math]q[/math]. Когда пересечение происходит снова слева направо (если оно вообще происходит), то автомат выходит из [math]x[/math] в состояние [math]p[/math]. Теперь, если 2ДКА перейдет в [math]x[/math] в состояние [math]q[/math] заново, то он снова может появиться в состоянии [math]p[/math]. Более того, состояние [math]p[/math] зависит исключительно от [math]q[/math] и [math]x[/math]. Обозначим такое отношение через [math]T_x(q) = p[/math]. Мы может записать все такие отношения в виде конечной таблицы [math]T_x : Q \cup \{d\} \to Q \cup \{h\}[/math], где [math]Q[/math] — множество состояний 2ДКА, а [math]d[/math] и [math]h[/math] будут описаны ниже.

На входной строке [math]xz[/math] 2ДКА начнет чтение с левого маркера конца строки. В процессе работы автомата позиция чтения будет меняться. В конце концов это позиция пересечет слева направо границу между [math]x[/math] и [math]z[/math]. В первый раз это произойдет в каком-нибудь состоянии, которое будем называть [math]T_x(d)[/math] (для этого мы и выделили [math]d[/math]). Так же автомат может никогда не выйти из [math]x[/math]. В таком случае мы запишем [math]T_x(d) = h[/math]. Состояние [math]T_x(d)[/math] дает немного информации о [math]x[/math], но только конечное количество, поскольку существует только конечное количество вариантов для [math]T_x(d)[/math]. Отметим, что [math]T_x(d)[/math] зависит только от [math]x[/math] и не зависит от [math]z[/math]. Если на вход подавалась бы строка [math]xw[/math] вместо [math]xz[/math], то в таком случае при пересечении границы из [math]x[/math] в [math]w[/math] автомат также был бы в состоянии [math]T_x(d)[/math], потому что его значение до того момента определялось только [math]x[/math] и до тех пор все, что находится справа от границы никак не влияет.

Если [math]T_x(d) = h[/math], то 2ДКА в бесконечном цикле внутри [math]x[/math], и он никогда не допустит и не отвергнет входную строку.

Предположим, что 2ДКА переходит из [math]x[/math] в [math]z[/math] и спустя время переходит обратно в состояние [math]q[/math]. Если это происходит, то потом:

  • либо снова произойдет переход из [math]x[/math] в некоторое состояние [math]p[/math]. В таком случае мы определим [math]T_x(q)=p[/math].
  • либо никогда не перейдет. В таком случае [math]T_x(q) = h[/math].

Ещё раз отметим, что [math]T_x(q)[/math] зависит только от [math]x[/math] и [math]q[/math] и не зависит от [math]z[/math]. Если автомат переходит в [math]x[/math] справа в состояние [math]q[/math], то тогда он появится заново в состоянии [math]T_x(q)[/math] (или никогда не перейдет, если [math]T_x(q) = h[/math]), потому что автомат детерминированный, и его поведение полностью определяется [math]x[/math] и состоянием, в которое он вошел.

Если мы запишем [math]T_x(q)[/math] для каждого состояния [math]q[/math] вместе с [math]T_x(d)[/math], это даст нам всю информацию о [math]x[/math], которую можно перенести через границу между [math]x[/math] и [math]z[/math]. Все это позволит узнать [math]T_x(d)[/math] сразу после пересечения границы, а также посмотреть значения [math]T_x(q)[/math]. Если [math]y[/math] — другая строка, такая что [math]T_y=T_x[/math], то тогда [math]x[/math] и [math]y[/math] будут неразличимы.

Заметим, что у нас конечное число возможных таблиц [math]T_x : Q \cup \{d\} \to Q \cup \{h\}[/math], а именно [math](k+1)^{k+1}[/math], где [math]k[/math] — размер множества [math]Q[/math]. Таким образом, у нас конечное количество информации о [math]x[/math], которое мы может перенести через границу справа от [math]x[/math], и которое закодировано у нас в таблицe [math]T_x[/math].

Отметим также, что если [math]T_x=T_y[/math] и автомат допускает строку [math]xz[/math], то тогда он допускает и строку [math]yz[/math], потому что последовательность состояний, перенесенных через границу [math]x[/math] и [math]z[/math] (либо [math]y[/math] и [math]z[/math]) в любом направлении, полностью определяется таблицами [math]T_x=T_y[/math] и строкой [math]z[/math]. Чтобы допустить строку [math]xz[/math], автомат должен в какой-то момент прочитать правый маркер конца строки, находясь в допускающем состоянии [math]t[/math].

Теперь мы может использовать теорему Майхилла-Нероуда, чтобы показать, что язык [math]L(M)[/math] нашего автомата [math]M[/math] регулярный.

[math]T_x = T_y \Rightarrow \forall z (M\ \text{accepts}\ xz \Leftrightarrow M\ \text{accepts}\ yz)[/math] [math] \Leftrightarrow \forall z (xz \in L(M)[/math] [math] \Leftrightarrow yz \in L(M)) \Leftrightarrow x \equiv_{L(M)} y[/math], где [math]\equiv_{L(M)}[/math]отношение эквивалентности на множестве слов в алфавите. Таким образом, если 2 строки имеют одинаковые таблицы, то тогда они эквивалентны отношением [math]\equiv_{L(M)}[/math]. Поскольку у нас только конечное число таблиц, отношение [math]\equiv_{L(M)}[/math] имеет только конечное количество классов эквивалентности, самое большее один для каждой таблицы. Следовательно, по теореме Майхилла-Нероуда, [math]L(M)[/math] — регулярный язык, что согласно теореме Клини, совпадает с классом и автоматных языков, ч.т.д.
[math]\triangleleft[/math]

Пример

Рассмотрим следующий язык [math]L_n = (a+b)^∗a(a+b)^{n-1}a(a+b)^∗[/math] при [math]\forall n \gt 0[/math].

Он может быть легко распознан с помощью следующего недетерминированного конечного автомата.

2dfa example 1.png

Теперь построим на его основе ДКА. Мы можем построить автомат [math]A_n[/math], который запоминает последние [math]n[/math] входных символов. Следовательно, когда мы находимся в состоянии, соответствующему подстроке [math]\sigma_1 \sigma_2 \dots \sigma_n[/math], и читаем очередной символ [math]\gamma[/math], то мы переходим в состояние, которому уже будет соответствовать подстрока [math]\sigma_2 \sigma_3 \dots \sigma_n \gamma[/math]. Однако, в случае [math]\sigma_1 = \gamma = a[/math] автомат переходит в допускающее состояние, где в цикле может переходить на любому символу. Следует отметить, что такая стратегия строит ДКА c [math]2^n + 1[/math] состояниями. Ниже представлен автомат [math]A_3[/math], который распознает язык [math]L_3[/math].

2dfa example 2.png

Покажем, что построенные таким образом автоматы будут минимальными.

  • Каждые две попарно различных строки [math]x[/math] и [math]y[/math] длины [math]n[/math] различимы. Чтобы доказать это, достаточно рассмотреть строку [math]b^{i-1}a[/math], где [math]i : 1 \leqslant i \leqslant n[/math] — самая левая позиция символа, в которой начинают различаться строки [math]x[/math] и [math]y[/math], и проверить, что ровно одна строка [math]xb^{i-1}a[/math] или [math]yb^{i-1}a[/math] принадлежит [math]L_n[/math].
  • Каждая строка длины [math]n[/math] не принадлежит [math]L_n[/math] и, следовательно, различима со строкой [math]a^{n+1}[/math], которая принадлежит [math]L_n[/math].
  • Таким образом, [math]2^n + 1[/math] строк в [math]\Sigma^n \cup \{a^{n+1}\}[/math] являются попарно различимыми для [math]L_n[/math]. Как следствие, [math]2^n + 1[/math] — минимальное количество состояний для ДКА, который способен распознать язык [math]L_n[/math].

Чтобы определить, что строка [math]w=c_1 \dots c_n[/math] принадлежит языку [math]L_n[/math], нужно для [math]\forall i = 1, \dots, |w|-n[/math] проверить, что [math]c_i=c_{i+n}=a[/math]. Строка будет допустимой, если условие сработает хотя бы для одного [math]i[/math]. Этот алгоритм может быть просто реализован с помощью 2ДКА. Будем для каждого [math]i[/math] двигаться на [math]n[/math] позиций вперед, а потом на [math]n-1[/math] позиций назад до позиции [math]i+1[/math]. Кроме того, при движении с позиции [math]i[/math] до [math]i+n[/math] автомат должен помнить сохраняется ли условие [math]c_i=a[/math]. Такой подход требует [math]O(n)[/math] состояний.

См. также

Источники информации