Acceptor (computer science)
In theoretical computer science, an acceptor is a special finite automaton . It is characterized by the fact that, unlike a transducer, it does not generate any output. It reads a word by accepting one input character for each processing step and after each read character either remains in the same state or changes to a new one. The input is accepted exactly when the acceptor terminates in a final state. Otherwise the word is discarded.
Acceptors are defined via an input alphabet , a set of states, a start state and acceptor states , as well as a state transition relation. If the state transition relation is a function, it is a deterministic finite automaton , otherwise it is a non-deterministic finite automaton .
The set of all words that an acceptor accepts is a formal language . Formal languages can be described with acceptors. The class of languages described by acceptors is equivalent to the class of languages described by regular expressions , namely regular languages .
Formally, a finite acceptor is defined by:
- a finite set of states Z,
- an initial state ,
- an input alphabet X,
- a state transition relation ,
- a lot of accepting states.
Known acceptors
- Finite automata , for regular languages (Chomsky type 3)
- Push-down automata , for context-free languages (Chomsky type 2)
- Deterministic push-down automata , for deterministic context-free languages
- Linearly bounded Turing machines , for context-sensitive languages (Chomsky type 1)
- Turing machines , for type 0 grammars (unbounded grammars)
See also
literature
- Renate Winter: Theoretical Computer Science . Basics with exercises and solutions. Oldenbourg, 2002, ISBN 3-486-25808-7 , pp. 74 ( limited preview in Google Book search).