Finite Automata

Definition of Nondeterministic Finite Automata with -Transitions



Subjects to be Learned

Contents

One of the objectives of this chapter is to show that there is a one-to-one correspondence between regular languages and finite automata. We are going to do that by showing that a finite automaton can be constructed from a given regular expression by combining simpler FAs using union, concatenation and Kleene star operations. These operations on FAs can be described conveniently if -Transitions are used. Basically an NFA with -Transitions is an NFA but can respond to an empty string and move to the next state. Here we are going to formally define NFA with -Transitions (abbreviated as NFA-) and see some examples. As we are going to see later, for any NFA- there is a NFA (hence DFA) which accepts the same language and vice versa.



Definition of nondeterministic finite automaton with -Transitions

Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q {} to 2Q ,   let q0 be a state in Q and let A be a subset of Q. We call the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.
Then a nondeterministic finite automaton with -Transitions is a 5-tuple < Q , , q0 , , A >

Notes on the definition
  1. A transition on reading means that the NFA- makes the transition without reading any symbol in the input. Thus the tape head does not move when is read.
  2. Note that any NFA is also a NFA-.



Example of NFA-

Q = { 0, 1, 2, 3, 4, 5 }, = { a, b }, A = , the initial state is 0 and is as shown in the following table.
           
State (q) Input (a) Next State ( (q, a) )
0 a { 1 }
0 { 4 }
1 { 2 }
2 { 3, 4 }
3 { 5 }
3 b { 4 }
4 a { 5 }













Here the transitions to are omitted from the table. A state transition diagram for this finite automaton is given below.



           



When a symbol a is read at the initial state 0, for example, it can move to any of the states other than 0. For once you are in state 1, for example, you can go to state 2, 3, 4 and 5 without reading any symbol on the tape. If you read string ab, then you come to state 4. For though you go to states 1, 2, 3, 4 and 5 by reading a, there are no transitions on reading b except from state 3. Thus 4 is the only state you can go to from the initial state by reading ab.



Test Your Understanding of Definition of NFA-

Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
There are two sets of questions.

The following notations are used in the questions:

   : \Lambda










Next -- Language Accepted by NFA-

Back to Study Schedule

Back to Table of Contents