The Setting
Two-way finite automata read their input written between a left endmarker and a right endmarker , and at each step move the head one cell to the left, keep it in place or move it one cell to the right. The model here is the two-way nondeterministic finite automaton (2NFA), with the two-way deterministic finite automaton (2DFA) as its deterministic case.
The input alphabet of interest is , the set of binary relations on a set .
The Tape
For a word over an alphabet , the tape of is , with cells numbered from the left. The tape symbol at a cell is the letter or endmarker written there: (1)✦
Relations and Their Products
The relation monoid of a set is the set of all binary relations with the product taken in path order and the identity relation : (2)✦
The relation product of a word over the alphabet is the element of given by (3)✦
The reflexive transitive closure of a relation on a set is the relation on joining to when a chain of zero or more -steps leads from to , the powers taken in : (4)✦
The Definition
Definition 1. Let be an input alphabet and a set of states. A two-way nondeterministic finite automaton over with state set consists of an initial state , a set of accepting states and a transition function (5)✦ giving, for each state and each scanned symbol, the allowed pairs of a next state and a move: to the left, to stay, to the right.
On an input of length , a configuration is a pair of a state and a cell , and the step relation of on is the relation on configurations given by (6)✦
The language of is the set of words on which a run of zero or more steps leads from the initial configuration , the head on , to a configuration in an accepting state, with the reflexive transitive closure (4) of : (7)✦
The automaton is a two-way deterministic finite automaton when each state and scanned symbol allow at most one move: (8)✦
For a set , the language over the alphabet is the set of words whose relation product (3) is nonempty: (9)✦
In the paper, the definitions read: a 2NFA has one initial state, a set of accepting states and transitions that depend on the state and the scanned symbol, with the moves left, stay and right, its head starts on the left endmarker and may not leave the endmarked tape, and it accepts when some finite computation reaches an accepting state, the initial configuration included; a 2DFA has at most one successor per state and symbol; and over the alphabet of binary relations on , with the path-order product and , the language is .
What Is Checked
The automaton (5) with its step relation (6), its language (7) and the deterministic case (8), and the language of (9), are stated over any input alphabet , any set of states and any set , on the tape symbols (1), the reflexive transitive closure (4), and the relation monoid (2) with its relation product (3).