Изменения

Перейти к: навигация, поиск
Нет описания правки
{{Определение
|definition=
'''Двусторонний детерминированный конечный автомат (2ДКА)''' (англ. ''Two-way deterministic finite automaton (2DFA)'') {{---}} набор из восьми элементов <tex>\langle \Sigma , Q, L, R, s \in Q, T \subset Qt, r, \delta : Q \times \Sigma \to Q \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>Tt \in Q</tex> {{---}} допускающее состояние (англ. ''accept state''), <tex>r \in Q</tex> — множество допускающих состояний отвергающее состояние (англ. ''set of accept statesreject state''), <tex>\delta: Q \times \{\Sigma \cup \{L, R\}\} \to Q \times \{left, right\}</tex> {{---}} функция переходов (англ. ''transition function'').
}}
Также должны быть удовлетворены следующие условия:
 
<tex>\forall q \in Q</tex>
* <tex>\delta(q, L) = (u, right)</tex> для некоторого <tex>u \in Q</tex>,
* <tex>\delta(q, R) = (v, left)</tex> для некоторого <tex>v \in Q</tex>,
и <tex>\forall b \in \Sigma \cup \{L\}</tex>
* <tex>\delta(t, b) = (t, right)</tex>,
* <tex>\delta(r, b) = (r, right)</tex>,
* <tex>\delta(t, R) = (t, left)</tex>,
* <tex>\delta(r, R) = (r, left)</tex>.
 
== См. также ==
* [[Детерминированные_конечные_автоматыДетерминированные конечные автоматы]]
== Источники информации==
418
правок

Навигация