Acceptor (computer science)

from Wikipedia, the free encyclopedia

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

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).

Web links