They can be seen in one of three intuitive, equivalent ways:
- the nondeterministic version of 2DFA
- one-tape, read-only, nondeterministic Turing Machines with tape limited to cells initially containing input
- 1NFAs that can go backwards while reading input symbols
They characterize Regular Languages as their deterministic counterpart.