Content deleted Content added
improve section organization |
merge content from Read-only right-moving Turing machines |
||
Line 143:
Another way of reducing the search space has been proposed in<ref>{{Cite book |doi = 10.1007/978-3-319-15579-1_48|chapter = BFS-Based Symmetry Breaking Predicates for DFA Identification|title = Language and Automata Theory and Applications|volume = 8977|pages = 611–622|series = Lecture Notes in Computer Science|year = 2015|last1 = Ulyantsev|first1 = Vladimir|last2 = Zakirzyanov|first2 = Ilya|last3 = Shalyto|first3 = Anatoly|isbn = 978-3-319-15578-4}}</ref> by means of new symmetry breaking predicates based on the [[breadth-first search]] algorithm:
the sought DFA's states are constrained to be numbered according to the BFS algorithm launched from the initial state. This approach reduces the search space by <math>C!</math> by eliminating isomorphic automata.
==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>.
==See also==
| |||