 |
Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA |
| << Closure of an FA |
| NFA with Null String >> |
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
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
Theory of
Automata
(CS402)
46
Table of Contents:
- What does automata mean, Introduction to languages
- Kleene Star Closure, Recursive definition of languages
- Regular Expression, Recursive definition of Regular Expression
- Equivalent Regular Expressions
- Finite Automaton
- Equivalent FAs
- FA corresponding to finite languages
- Examples of TGs: accepting all strings
- Generalized Transition Graphs
- Nondeterminism, Kleene’s Theorem
- Proof(Kleene’s Theorem Part II)
- Kleene’s Theorem Part III
- Concatenation of FAs
- Closure of an FA
- Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
- NFA with Null String
- NFA and Kleene’s Theorem
- NFA corresponding to Concatenation of FAs
- Distinguishable strings and Indistinguishable strings
- Finite Automaton with output, Moore machine
- Mealy machine
- Equivalent machines
- Mealy machines in terms of sequential circuit
- Regular languages, Complement of a language
- Nonregular languages
- Pumping Lemma
- Pumping Lemma version II
- Pseudo theorem
- Decidability
- finiteness of a language
- Context Free Grammar (CFG), CFG terminologies
- Trees
- Polish Notation (o-o-o)
- Total language tree, Regular Grammar
- Null Production
- Chomsky Normal Form (CNF)
- A new format for FAs
- Nondeterministic PDA
- PDA corresponding to CFG
- Conversion form of PDA
- Conversion Form, Joints of the machine
- Row language, Nonterminals
- Non-Context-Free language, Pumping lemma for CFLs
- Decidablity, Parsing Techniques
- Turing machine