- Nondeterministic finite automata
- State transition diagram
- State transition table

This is so to say the essence of such an FA. But it is not DFA. A DFA that accepts { a } would need more states and transitions as you can see below for example.

Without those extra state and transitions it is not a DFA if the alphabet is { a , b } .

To avoid those redundant states and transitions and to make modeling easier we use finite automata called nondeterministic finite automata (abbreviated as NFA) . Below we are going to formally define nondeterministic finite automata (abbreviated as NFS) and see some examples. As we are going to see later, for any NFA there is a DFA which accepts the same language and vice versa.

NFAs are quite similar to DFAs. The only difference is in the transition function. NFAs do not necessarily go to a unique next state. An NFA may not go to any state from the current state on reading an input symbol or it may select one of several states nondeterministically (e.g. by throwing a die) as its next state.

Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to 2

Then a

- As in the case of DFA the set Q in the above definition is simply a set with a finite number of elements. Its elements can be interpreted as a state that the system (automaton) is in.
- The transition function is also called a
**next state function**. Unlike DFAs an NFA moves into one of the states given by (q, a) if it receives the input symbol a while in state q. Which one of the states in (q, a) to select is determined nondeterministically. - Note that is a function. Thus for
**each state**q of Q and for**each symbol**a of (q, a) must be specified. But it can be the empty set, in which case the NFA aborts its operation. - As in the case of DFA the accepting states are used to distinguish sequences of inputs given to the finite automaton. If the finite automaton is in an accepting state when the input ends i.e. ceases to come, the sequence of input symbols given to the finite automaton is "accepted". Otherwise it is not accepted.
- Note that any DFA is also a NFA.

State (q) | Input (a) | Next State ( (q, a) ) |

0 | a | { 1 } |

1 | a |

A state transition diagram for this finite automaton is given below.

If the alphabet is changed to { a, b } in stead of { a }, this is still an NFA that accepts { a } .

State (q) | Input (a) | Next State ( (q, a) ) |

0 | a | { 1 , 2 } |

0 | b | |

1 | a | |

1 | b | { 2 } |

2 | a | |

2 | b |

Note that for each state there are two rows in the table for corresponding to the symbols a and b, while in the Example 1 there is only one row for each state.

A state transition diagram for this finite automaton is given below.

Let us see how an automaton operates when some inputs are applied to it. As an example let us consider the automaton of Example 2 above.

Initially it is in state 0. When it reads the symbol a, it moves to either state 1 or state 2. Since the state 2 is the accepting state, if it moves to state 2 and no more inputs are given, then it stays in the accepting state. We say that this automaton accepts the string a. If on the other hand it moves to state 1 after reading a, if the next input is b and if no more inputs are given, then it goes to state 2 and remains there. Thus the string ab is also accepted by this NFA. If any other strings are given to this NFA, it does not accept any of them.

Let us now define the function

Click Yes or No , then Submit.

There are two sets of questions.

The following notations are used in the questions: