print · source · login   

(redirected from Syntax.NFA)

Acceptor Automaton

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.

Formal definition

Source: and

A finite acceptor FA is a 5-tuple, (Q, Σ, δ, q0, 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))
  • an initial or start state (q0Q)
  • a set of accept states (FQ)

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

Model definitions

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.
A non-deterministic finite acceptor is a finite acceptor which is NOT input deterministic.
A deterministic finite acceptor is a finite acceptor which is input deterministic.



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

Figure 1 The state diagram for M

M = (Q, Σ, δ, q0, F) where


The state S1 represents that there has been an even number of 0s in the input so far, while S2 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 S1, 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".