请输入您要查询的百科知识：

　

词条 Two-way finite automaton
释义

  1. Two-way deterministic finite automaton

  2. Formal description

  3. Two-way nondeterministic finite automaton

  4. Two-way alternating finite automaton

  5. State complexity tradeoffs

  6. Sweeping automata

  7. Two-way quantum finite automaton

  8. Two-way pushdown automaton

  9. References

In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.

Two-way deterministic finite automaton

A two-way deterministic finite automaton (2DFA) is an abstract machine, a generalized version of the deterministic finite automaton (DFA) which can revisit characters already processed. As in a DFA, there are a finite number of states with transitions between them based on the current character, but each transition is also labelled with a value indicating whether the machine will move its position in the input to the left, right, or stay at the same position. Equivalently, 2DFAs can be seen as read-only Turing machines with no work tape, only a read-only input tape.

2DFAs were introduced in a seminal 1959 paper by Rabin and Scott,[1] who proved them to have equivalent power to one-way DFAs. That is, any formal language which can be recognized by a 2DFA can be recognized by a DFA which only examines and consumes each character in order. Since DFAs are obviously a special case of 2DFAs, this implies that both kinds of machines recognize precisely the class of regular languages. However, the equivalent DFA for a 2DFA may require exponentially many states, making 2DFAs a much more practical representation for algorithms for some common problems.

2DFAs are also equivalent to read-only Turing machines that use only a constant amount of space on their work tape, since any constant amount of information can be incorporated into the finite control state via a product construction (a state for each combination of work tape state and control state).

Formal description

Formally, a two-way deterministic finite automaton can be described by the following 8-tuple: where

  • is the finite, non-empty set of states
  • is the finite, non-empty set of input alphabet
  • is the left endmarker
  • is the right endmarker
  • is the start state
  • is the end state
  • is the reject state

In addition, the following two conditions must also be satisfied:

  • For all

for some

for some

It says that there must be some transition possible when pointer on the alphabet reaches the end.

  • For all symbols

It says that once the automaton reaches the accept or reject state, it stays in there forever and the pointer goes to the right most symbol and cycles there infinitely.[2]

Two-way nondeterministic finite automaton

A two-way nondeterministic finite automaton (2NFA) may have multiple transitions defined in the same configuration. Its transition function is

  • .

Like a standard one-way NFA, a 2NFA accepts a string if at least one of the possible computations is accepting. Like the 2DFAs, the 2NFAs also accept only regular languages.

Two-way alternating finite automaton

A two-way alternating finite automaton (2AFA) is a two-way extension of an alternating finite automaton (AFA). Its state set is

  • where .

States in and are called existential resp. universal. In an existential state a 2AFA nondeterministically chooses the next state like an NFA, and accepts if at least one of the resulting computations accepts. In a universal state 2AFA moves to all next states, and accepts if all the resulting computations accept.

State complexity tradeoffs

{{Main|State complexity}}

Two-way and one-way finite automata, deterministic and nondeterministic and alternating, accept the same class of regular languages. However, transforming an automaton of one type to an equivalent automaton of another type incurs a blow-up in the number of states. Kapoutsis[3] determined that transforming an -state 2DFA to an equivalent DFA requires states in the worst case. If an -state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is . Ladner, Lipton and Stockmeyer.[4]

proved that an -state 2AFA can be converted to a DFA with states.

The 2AFA to NFA conversion requires states in the worst case,

see Geffert and Okhotin.[5]

{{unsolved|computer science|Does every -state 2NFA have an equivalent -state 2DFA?}}

It is an open problem whether every 2NFA can be converted to a 2DFA

with only a polynomial increase in the number of states.

The problem was raised by Sakoda and Sipser,[6]

who compared it to the P vs. NP problem

in the computational complexity theory.

Berman and Lingas[7] discovered a formal relation between this problem

and the L vs. NL open problem,

see Kapoutsis[8] for a precise relation.

Sweeping automata

Sweeping automata are 2DFAs of a special kind that process the input string by making alternating left-to-right and right-to-left sweeps, turning only at the endmarkers. Sipser[9] constructed a sequence of languages, each accepted by an n-state NFA, yet which is not accepted by any sweeping automata with fewer than states.

Two-way quantum finite automaton

The concept of 2DFAs was in 1997 generalized to quantum computing by John Watrous's "On the Power of 2-Way Quantum Finite State Automata", in which he demonstrates that these machines can recognize nonregular languages and so are more powerful than DFAs.

[10]

Two-way pushdown automaton

A pushdown automaton that is allowed to move either way on its input tape is called two-way pushdown automaton (2PDA);[11]

it has been studied by Hartmanis, Lewis, and Stearns (1965).[12]

Aho, Hopcroft, Ullman (1968)[13]

and Cook (1971)[14] characterized the class of languages recognizable by deterministic (2DPDA) and non-deterministic (2NPDA) two-way pushdown automata;

Gray, Harrison, and Ibarra (1967) investigated the closure properties of these languages. [15]

References

1. ^{{cite journal| last = Rabin| first = Michael O.| last2 = Scott| first2 = Dana| date = 1959| title = Finite automata and their decision problems| url = | journal = IBM Journal of Research and Development| volume = 3| issue = 2| pages = 114–125| doi = 10.1147/rd.32.0114| access-date = }}
2. ^This definition has been taken from lecture notes of CS682 (Theory of Comoputation) by Dexter Kozen of Stanford University
3. ^{{cite conference| title = Removing Bidirectionality from Nondeterministic Finite Automata| first = Christos| last = Kapoutsis| year = 2005| conference = MFCS 2005| editor = J. Jedrzejowicz, A.Szepietowski| volume = 3618| book-title = Mathematical Foundations of Computer Science| publisher = Springer| location =| pages = 544–555| doi = 10.1007/11549345_47}}
4. ^{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}
5. ^{{cite book|last1=Geffert|first1=Viliam|title=Mathematical Foundations of Computer Science 2014|last2=Okhotin|first2=Alexander|chapter=Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata|volume=8634|year=2014|pages=291–302|issn=0302-9743|doi=10.1007/978-3-662-44522-8_25|series=Lecture Notes in Computer Science|isbn=978-3-662-44521-1}}
6. ^{{cite conference| title = Nondeterminism and the Size of Two Way Finite Automata| first1 = William J.| last1 = Sakoda| first2 = Michael| last2 = Sipser| year = 1978| conference = STOC 1978| publisher = ACM| location =| pages = 275–286| doi = 10.1145/800133.804357}}
7. ^{{cite conference| title = On the complexity of regular languages in terms of finite automata| first1 = Piotr| last1 = Berman| first2 = Andrzej| last2 = Lingas| year = 1977| volume = Report 304| publisher = Polish Academy of Sciences}}
8. ^{{cite journal| last = Kapoutsis| first = Christos A.| date = 2014| title = Two-Way Automata Versus Logarithmic Space| journal = Theory of Computing Systems| volume = 55| issue = 2| pages = 421–447| doi = 10.1007/s00224-013-9465-0}}
9. ^{{cite journal| last = Sipser| first = Michael| date = 1980| title = Lower Bounds on the Size of Sweeping Automata| journal = Journal of Computer and System Sciences| volume = 21| issue = 2| pages = 195–202| doi = 10.1016/0022-0000(80)90034-3}}
10. ^John Watrous. On the Power of 2-Way Quantum Finite State Automata. CS-TR-1997-1350. 1997. pdf
11. ^{{cite book|author1=John E. Hopcroft |author2=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=978-0-201-02988-8}} Here: p.124; this paragraph is omitted in the 2003 edition.
12. ^{{cite book|author1=J. Hartmanis |author2=P.M. Lewis II, R.E. Stearns| chapter=Hierarchies of Memory Limited Computations| title=Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design| year=1965| pages=179–190}}
13. ^{{cite journal|author1=Alfred V. Aho |author2=John E. Hopcroft |author3=Jeffrey D. Ullman | title=Time and Tape Complexity of Pushdown Automaton Languages| journal=Information and Control| year=1968| volume=13| number=3| pages=186–206| doi=10.1016/s0019-9958(68)91087-5}}
14. ^{{cite book| author=S.A. Cook| chapter=Linear Time Simulation of Deterministic Two-Way Pushdown Automata| title=Proc. IFIP Congress| year=1971| pages=75–80| publisher=North Holland}}
15. ^{{cite journal|author1=Jim Gray |author2=Michael A. Harrison |author3=Oscar H. Ibarra | title=Two-Way Pushdown Automata| journal=Information and Control| year=1967| volume=11| number=1–2| pages=30–70| doi=10.1016/s0019-9958(67)90369-5}}

1 : Finite automata
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/13 11:54:14