Finite Automata
Definition of Nondeterministic Finite Automata with -Transitions
Subjects to be Learned
- Nondeterministic finite automata with -Transitions
- State transition diagram
- State transition table
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
- 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.
- 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