ZeePedia

NFA with Null String

<< Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
NFA and Kleene’s Theorem >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 16
Reading Material
Chapter 7
Introduction to Computer Theory
Summary
Applying an NFA on an example of maze, NFA with null string, examples, RE corresponding to NFA with null
string (task), converting NFA to FA (method 1,2,3) examples
Application of an NFA
There is an important application of an NFA in artificial intelligence, which is discussed in the following
example of a maze
1
2
3
-
4
L
5
O
6
M
7
P
8
N
9
+
- and + indicate the initial and final states respectively. One can move only from a box labeled by other then L,
M, N, O, P to such another box. To determine the number of ways in which one can start from the initial state
and end in the final state, the following NFA using only single letter a, can help in this regard
a
a
a
3
-
1
2
a
a
a
a
a
a
a
4
5
a
a
a
a
a
a
a
6
7
8
9
+
a
a
a
It can be observed that the shortest path which leads from the initial state and ends in the final state, consists of
six steps i.e. the shortest string accepted by this machine is aaaaaa. The next larger accepted string is aaaaaaaa.
Thus if this NFA is considered to be a TG then the corresponding regular expression may be written as
aaaaaa(aa)*
Which shows that there are infinite many required ways
Note
It is to be noted that every FA can be considered to be an NFA as well , but the converse may not true.
It may also be noted that every NFA can be considered to be a TG as well, but the converse may not true.
It may be observed that if the transition of null string is also allowed at any state of an NFA then what will be
the behavior in the new structure. This structure is defined in the following
NFA with Null String
Definition
If in an NFA, Y is allowed to be a label of an edge then the NFA is called NFA with Y (NFA-Y).
An NFA-Y is a collection of three things
Finite many states with one initial and some final states.
Finite set of input letters, say, S = {a, b, c}.
Finite set of transitions, showing where to move if a letter is input at certain state.
47
img
Theory of Automata
(CS402)
There may be more than one transitions for certain letter and there may not be any transition
for a certain letter. The transition of Y is also allowed at any state.
Example
Consider the following NFA with Null string
a,b
b
L
+
1
­
The above NFA with Null string accepts the language of strings, defined over Σ = {a, b}, ending in b.
Example
Consider the following NFA with Null string
a,b
L, a
a
+
1
­
The above NFA with Null string accepts the language of strings, defined over Σ = {a, b}, ending in a.
Note
It is to be noted that every FA may be considered to be an NFA-Y as well, but the converse may not true.
Similarly every NFA-Y may be considered to be a TG as well, but the converse may not true.
NFA to FA
Two methods are discussed in this regard.
Method 1: Since an NFA can be considered to be a TG as well, so a RE corresponding to the given NFA can be
determined (using Kleene's theorem). Again using the methods discussed in the proof of Kleene's theorem, an
FA can be built corresponding to that RE. Hence for a given NFA, an FA can be built equivalent to the NFA.
Examples have, indirectly, been discussed earlier.
Method 2: Since in an NFA, there may be more than one transition for a certain letter and there may not be any
transition for certain letter, so starting from the initial state corresponding to the initial state of given NFA, the
transition diagram of the corresponding FA, can be built introducing an empty state for a letter having no
transition at certain state and a state corresponding to the combination of states, for a letter having more than
one transitions. Following are the examples
2
Example
Consider the following NFA
b
a
1-
4+
a
b
3
Using the method discussed earlier, the above NFA may be equivalent to the following FA
a
1-
2
b
b
4+
a
a
a, b
b
3
a, b
48
img
Theory of Automata
(CS402)
Example
A simple NFA that accepts the language of strings defined over S = {a,b}, consists of bb and bbb
b
b
b
b
2
3
4+
1-
The above NFA can be converted to the following FA
b
b
b
2
4+
(3,4)+
1-
a
a
a
a,b
a, b
Method 3: As discussed earlier that in an NFA, there may be more than one transition for a certain letter and
there may not be any transition for certain letter, so starting from the initial state corresponding to the initial
state of given NFA, the transition table along with new labels of states, of the corresponding FA, can be built
introducing an empty state for a letter having no transition at certain state and a state corresponding to the
combination of states, for a letter having more than one transitions. Further examples are discussed in the next
lecture.
49