ZeePedia

Nondeterminism, Kleene’s Theorem

<< Generalized Transition Graphs
Proof(Kleene’s Theorem Part II) >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 10
Reading Material
Chapter 6, 7
Introduction to Computer Theory
Summary
Examples of GTG accepting the languages of strings: containing aa or bb, beginning with and ending in same
letters, beginning with and ending in different letters, containing aaa or bbb,
Nondeterminism, Kleene's theorem (part I, part II, part III), proof of Kleene's theorem part I
Example
Consider the language L of strings, defined over Σ = {a,b}, containing double a or double b. The language L
can be expressed by the following regular expression (a+b)* (aa + bb) (a+b)*
The language L may be accepted by the following GTG.
Example
Consider the Language L of strings, defined over Σ = {a, b}, beginning with and ending in same letters.
The language L may be expressed by the following regular expression (a+b)+ a(a + b)*a + b(a + b)*b.
This language may be accepted by the following GTG
Example
Example
Consider the language L of strings of, defined over Σ = {a, b}, beginning and ending in different letters.
a(a + b)*b + b(a + b)*a
The language L may be expressed by RE
The language L may be accepted by the following GTG
The language L may be accepted by the following GTG as well
Example
Consider the language L of strings, defined over Σ = {a, b}, having triple a or triple b. The language L may be
expressed by RE (a+b)* (aaa + bbb) (a+b)*
This language may be accepted by the following GTG
28
img
Theory of Automata
(CS402)
Nondeterminism
TGs and GTGs provide certain relaxations i.e. there may exist more than one path for a certain string or there
may not be any path for a certain string, this property creates nondeterminism and it can also help in
differentiating TGs or GTGs from FAs. Hence an FA is also called a Deterministic Finite Automaton (DFA).
Kleene's Theorem
If a language can be expressed by
FA or
TG or
RE
then it can also be expressed by other two as well.
It may be noted that the theorem is proved, proving the following three parts
Kleene's Theorem Part I
If a language can be accepted by an FA then it can be accepted by a TG as well.
Kleene's Theorem Part II
If a language can be accepted by a TG then it can be expressed by an RE as well.
Kleene's Theorem Part III
If a language can be expressed by a RE then it can be accepted by an FA as well.
Proof(Kleene's Theorem Part I)
Since every FA can be considered to be a TG as well, therefore there is nothing to prove.
29