 |
NFA with Null String |
| << Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA |
| NFA and Kleene’s Theorem >> |
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
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
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
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