*(redirected from Syntax.DFA)*

Acceptors, also called recognizers and sequence detectors, produce binary output, indicating whether or not the received input is accepted. Each state of an acceptor is either "accepting" or "rejecting".

An Acceptor Automaton can define a language; words of actions leading to an accepting state are in the language and words leading to rejecting states are not in the language. By definition, the languages accepted by Acceptor Automaton are the regular languages. A language is regular if there is some Acceptor Automaton that accepts it.

**Source:** http://www.wikiwand.com/en/Deterministic_finite_automaton and http://www.wikiwand.com/en/Finite-state_machine

A finite acceptor *FA* is a 5-tuple, (*Q*, Σ, δ, *q*_{0}, *F*), consisting of

- a finite set of states (
*Q*) - a finite set of input symbols called the alphabet (Σ)
- a transition function
- for Deterministic Finite Automaton(DFA): (δ :
*Q*× Σ →*Q*) - for Non-deterministic Finite Automaton(NFA): (δ :
*Q*× Σ →*P(Q)*)

- for Deterministic Finite Automaton(DFA): (δ :
- an initial or start state (
*q*_{0}∈*Q*) - a set of accept states (
*F*⊆*Q*)

Here, P(Q) denotes the power set of Q, meaning the transition function δ returns a set of states.

- FA
- A finite acceptor is a structure consisting of locations with transitions between them. Each location is marked either active or inactive. Each transistion of the system can be triggered by its input, causing the system to go to another location.
- NFA
- A non-deterministic finite acceptor is a finite acceptor which is NOT input deterministic.
- DFA
- A deterministic finite acceptor is a finite acceptor which is input deterministic.

**Source:** http://www.wikiwand.com/en/Deterministic_finite_automaton

The following example is of a DFA *M*, with a binary alphabet, which requires that the input contains an even number of 0s.

*M* = (*Q*, Σ, δ, *q _{0}*,

*Q*= {*S*_{1},*S*_{2}},- Σ = {0, 1},
*q*=_{0}*S*_{1},*F*= {*S*_{1}}, and- δ is defined by the following state transition table:

0 | 1 | |

S_{1} | S_{2} | S_{1} |

S_{2} | S_{1} | S_{2} |

The state *S*_{1} represents that there has been an even number of 0s in the input so far, while *S*_{2} signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not. If the input did contain an even number of 0s, *M* will finish in state *S*_{1}, an accepting state, so the input string will be accepted.

The language recognized by *M* is the regular language given by the regular expression (1 + 0 (1*) 0)*, where "*" is the Kleene star, e.g., 1* denotes any non-negative number (possibly zero) of symbols "1".