ZeePedia buy college essays online


Theory of Automata

<<< Previous Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA Next >>>
 
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 15
Reading Material
Chapter 7
Introduction to Computer Theory
Summary
Examples of Kleene's theorem part III (method 3), NFA, examples, avoiding loop using NFA, example,
converting FA to NFA, examples, applying an NFA on an example of maze
Note
It is to be noted that as observed in the examples discussed in previous lecture, if at the initial state of the given
FA, there is either a loop or an incoming transition edge, the initial state corresponds to the final state and a non-
final state as well, of the required FA, otherwise the initial state of given FA will only correspond to a single
state of the required FA (i.e. the initial state which is final as well).
Nondeterministic Finite Automaton (NFA)
Definition
An NFA is a TG with a unique start state and a property of having single letter as label of transitions. An NFA 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 (Y is not a valid transition),
there may be more than one transition for certain letters and there may not be any transition for certain letters.
Observations
It may be observed, from the definition of NFA, that the string is supposed to be accepted, if there exists at least
one successful path, otherwise rejected.
It is to be noted that an NFA can be considered to be an intermediate structure between FA and TG.
The examples of NFAs can be found in the following
2+
a
Example
a
1-
3
a
b
4
5+
It is to be noted that the above NFA accepts the language consisting of a and ab.
a,b
a,b
Example
a
a
3+
2
1-
It is to be noted that the above NFA accepts the language of strings, defined over Σ = {a, b}, containing aa.
Note
It is to be noted that NFA helps to eliminate a loop at certain state of an FA. This process is done converting the
loop into a circuit. But during this process the FA remains no longer FA and is converted to a corresponding
NFA, which is shown in the following example.
...
...
4
8
a
a
b
Example
c
b
...
7
9
...
5
Consider a part of the following FA with an
alphabet Σ = {a,b,c,d}
c
d
...
10 ...
6
44
img
Theory of Automata
(CS402)
To eliminate the loop at state 7, the corresponding NFA may be as follows
b
...
...
11
4
8
c
a
d
a
a
...
...
9
5
b
b
c
c
d
10 ...
...
6
7
Converting an FA to an equivalent NFA
It is to be noted that according to the Kleene's theorem, if a language can be accepted by an FA, then there
exists a TG accepting that language. Since, an NFA is a TG as well, therefore there exists an NFA accepting the
language accepted by the given FA. In this case these FA and NFA are said to be equivalent to each others.
Following are the examples of FAs to be converted to the equivalent NFAs
Example
Consider the following FA corresponding to (a+b)*b
b
a
b
-
+
a
The above FA may be equivalent to the following NFA
a,b
b
+
­
Can the structure of above NFA be compared with the corresponding RE ?
Example
a,b
b
a
Consider the following FA
a
+
1
­
b
The above FA may be equivalent to the following NFA
a, b
a, b
a
a
+
1
­
Can the structure of above NFA be compared with the corresponding RE ?
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
+
45
img
Theory of Automata
(CS402)
46