Editing Deterministic finite automaton (section)

==Equivalent models==

===Read-only right-moving Turing machines===

'''Read-only right-moving Turing machines''' are a particular type of [[Turing machine]] that only moves right; these
are almost exactly equivalent to DFAs.<ref name=RORMTM>{{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker | title = Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994| isbn =0-12-206382-1}}</ref>
The definition based on a singly infinite tape is a 7-[[tuple]]

: <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle,</math>
where
: <math>Q</math> is a finite set of ''states'';
: <math>\Gamma</math> is a finite set of the ''tape alphabet/symbols'';
: <math>b \in \Gamma</math> is the ''blank symbol'' (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
: <math>\Sigma</math>, a subset of <math>\Gamma</math> not including ''b'', is the set of ''input symbols'';
: <math>\delta: Q \times \Gamma \to Q \times \Gamma \times \{R\}</math> is a [[Function (mathematics)|function]] called the ''[[State transition system|transition function]]'', ''R'' is a right movement (a right shift);
: <math>q_0 \in Q</math> is the ''initial state'';
: <math>F \subseteq Q</math> is the set of ''final'' or ''accepting states''.

The machine always accepts a regular language. There must exist at least one element of the set {{mvar|F}} (a '''HALT''' state) for the language to be nonempty.

====Example of a 3-state, 2-symbol read-only Turing machine====

{|class="wikitable"
|-
|
| colspan="3" | Current state '''A'''
| colspan="3" | Current state '''B'''
| colspan="3" | Current state '''C'''
|-
! tape symbol 
! Write symbol
! Move tape
! Next state
! Write symbol
! Move tape
! Next state
! Write symbol
! Move tape
! Next state
|-
! 0
 | 1
 | R
|style="font-weight:bold" | B
 | 1
 | R
|style="font-weight:bold" | A
 | 1
 | R
|style="font-weight:bold" | B
|-
! 1
 | 1
 | R
|style="font-weight:bold" | C
 | 1
 | R
|style="font-weight:bold" | B
 | 1
 | N
 | '''HALT'''
|}

: <math>Q = \{ A, B, C, \text{HALT} \};</math>
: <math>\Gamma = \{ 0, 1 \};</math>
: <math>b = 0</math>, "blank";
: <math>\Sigma = \varnothing</math>, empty set;
: <math>\delta = </math> see state-table above;
: <math>q_0 = A</math>, initial state;
: <math>F = </math> the one element set of final states: <math>\{\text{HALT}\}</math>.