Non-deterministic Finite Automaton - Automata Theory

What is Non-deterministic Finite Automaton?

In NDFA, the machine will rotate across the combination of the states for a particular input symbol. This is also known as, we cannot be determining the exact states of the machine. So it also called as Non-deterministic Automaton. Incase if it includes finite number of states, then the machine is called Non-deterministic Finite Machine or Non-deterministic Finite Automaton.

Formal Definition of an NDFA

An NDFA is highlighted by a 5-tuple (Q, ∑, δ,q0, F) where −

  • Q is a finite set of states.
  • ∑ is a finite set of symbols called the alphabets.
  • δ is the transition function where non
  • (Here the power set of non has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)
  • q0 is the initial state from where any input is processed (q0∈ Q).
  • F is a set of final state/states of Q (F ⊆ Q).

Graphical Representation of an NDFA: (same as DFA)

An NDFA cal also presented by digraphs called state diagram.

  • The vertices represent the states.
  • The arcs labeled with an input alphabet show the transitions.
  • The initial state is denoted by an empty single incoming arc.
  • The final state is indicated by double circles.

Example

Let a non-deterministic finite automaton be →

  • Q = {a, b, c}
  • ∑ = {0, 1}
  • q0= {a}
  • F = {c}

The transition function δ as shown below −

Present State Next State for Input 0 Next State for Input 1
a a, b b
b c a, c
c b, c c

Its graphical representation would be as follows −

ndfa_graphical_representation

DFA vs NDFA

Let’s see the below table which lists the differences between DFA and NDFA.

DFA NDFA
The transition from a state is to a single particular next state for each input symbol. Hence it is calleddeterministic. The transition from a state can be to multiple next states for each input symbol. Hence it is callednon-deterministic.
Empty string transitions are not seen in DFA. NDFA permits empty string transitions.
Backtracking is allowed in DFA In NDFA, backtracking is not always possible.
Requires more space. Requires less space.
A string is accepted by a DFA, if it transits to a final state. A string is accepted by a NDFA, if at least one of all possible transitions ends in a final state.

Acceptors, Classifiers, and Transducers

Acceptor (Recognizer)

An automaton which provides a Boolean function is termed as an acceptor. Here the states which includes all the states of an acceptor is either accepting or rejecting the inputs given to it.

Classifier

A classifier includes more than two final states and provides a single output at the end.

Transducer

An automaton which provides outputs based on current input and/or previous state is called a transducer. Transducers may be two types −

  • Mealy Machine − The output depends both on the current state and the current input.
  • Moore Machine − The output depends only on the current state.

Acceptability by DFA and NDFA

While a string is received by a DFA/NDFA iff the DFA/NDFA strats at the basic state and closed in an accepting state (any of the final states) once the strong reading sone.

A string S is accepted by a DFA/NDFA (Q, ∑, δ,q0, F), iff

δ*(q0, S) ∈ F

The language L accepted by DFA/NDFA is

{S | S ∈ ∑* and δ*(q0, S) ∈ F}

A string S′ is not accepted by a DFA/NDFA (Q, ∑, δ,q0, F), iff

δ*(q0, S′) ∉ F

The language L′ not accepted by DFA/NDFA (Complement of accepted language L) is

{S | S ∈ ∑* and δ*(q0, S) ∉ F}

Example

Let’s assume that the DFA shown in Figure 1.3. From the DFA, the acceptable strings can be derived.

acceptability_of_strings_by_dfa

Strings accepted by the above DFA: {0, 00, 11, 010, 101, ...........}

Strings not accepted by the above DFA: {1, 011, 111, ........}

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics