minicomplexity
2FA
definition

A formal machine consisting of a finite control which draws its input symbols from an end-marked, read-only tape via a two-way head.

details

sketch of a 2FA A two-way finite automaton is a tuple

$M=(S,\varSigma,\delta,q_0,F)$
of a finite non-empty set of states $S$, a finite non-empty input alphabet $\varSigma$, a designated start state $q_0\in S$, a set of designated accepting states $F\subseteq S$, and a transition function $\delta$ which associates
pairs from $S\times(\varSigma\cup\{{\vdash},{\dashv}\})$ with pairs in $S\times\{{\scriptstyle\text L},{\scriptstyle\text R}\}$,
where $\vdash$ and $\dashv$ are two special end-marking symbols, and $\scriptstyle\text L$ and $\scriptstyle\text R$ denote the left and right directions on the tape. We assume that no pair of the form $(\,\cdot\,,{\vdash})$ is associated with a pair of the form $(\,\cdot\,,{\scriptstyle\text L})$, and that a pair of the form $(\,\cdot\,,{\dashv})$ is associated with a pair of the form $(q,{\scriptstyle\text R})$ only if $q\in F$.

An input $w\in\varSigma^\ast$ is presented on the tape surrounded by the end-markers, as ${\vdash}\,w\,{\dashv}$. The computation starts with the control at state $q_0$ and with the head positioned on $\vdash$. At every step, the possibilities for the next state and position are derived from the $\delta$-associations of the current state and symbol. In the resulting computation tree, each branch can eventually either continue forever, and we call it looping; or reach a state and a symbol with no possible next state and position, and we call it hanging; or fall off $\dashv$ into an accepting state, and we call it accepting. (By our assumptions for the behavior of $\delta$ on the end-markers, we know that no other possibility exists.)

notes

First introduced with a single-pass head and in the deterministic mode, as a 2DFA, by Rabin 1957.

restrictions:
1DFA 1NFA 1FA RDFA RNFA RFA SDFA SNFA SFA 2DFA 2NFA
generalizations:
– no record –
related classes:
2D 22D e2D r2D f2D 2N 22N e2N r2N f2N re-2D re-22D re-e2D re-r2D re-f2D re-2N re-22N re-e2N re-r2N re-f2N co-2D co-22D co-e2D co-r2D co-f2D co-2N co-22N co-e2N co-r2N co-f2N rc-2D rc-22D rc-e2D rc-r2D rc-f2D rc-2N rc-22N rc-e2N rc-r2N rc-f2N 2D/uny 22D/uny e2D/uny r2D/uny f2D/uny 2N/uny 22N/uny e2N/uny r2N/uny f2N/uny re-2D/uny re-22D/uny re-e2D/uny re-r2D/uny re-f2D/uny re-2N/uny re-22N/uny re-e2N/uny re-r2N/uny re-f2N/uny co-2D/uny co-22D/uny co-e2D/uny co-r2D/uny co-f2D/uny co-2N/uny co-22N/uny co-e2N/uny co-r2N/uny co-f2N/uny rc-2D/uny rc-22D/uny rc-e2D/uny rc-r2D/uny rc-f2D/uny rc-2N/uny rc-22N/uny rc-e2N/uny rc-r2N/uny rc-f2N/uny