 |
Examples of TGs: accepting all strings |
| << FA corresponding to finite languages |
| Generalized Transition Graphs >> |
Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 8
Reading
Material
Chapter
6
Introduction
to Computer Theory
Summary
Examples
of TGs: accepting all
strings, accepting none,
starting with b, not ending
in b, containing aa,
containing
aa or bb
Note
It is to be
noted that in TG there may
exist more than one paths
for certain string, while there
may not exist
any
path
for certain string as well. If there
exists at least one path
for a certain string, starting from
initial state and
ending in a
final state, the string is
supposed to be accepted by the
TG, otherwise the string is supposed to
be
rejected.
Obviously collection of accepted strings
is the language accepted by
the TG.
Example
Consider
the Language L , defined over Σ =
{a, b} of all
strings including Λ. The
language L may be
accepted
a,b
a,b
by the
following TG
L
+
The
language L may also be
accepted by the following
TG
a,b
TG1
±
a,b
a,
b
±
+
TG2
Example
Consider
the following TGs
TG1
-
a,
b
TG2
-
1
a,b
a,
b
-
1
TG3
It may be
observed that in the first
TG, no transition has been
shown. Hence this TG does
not accept any
string,
defined
over any alphabet. In TG2 there are transitions
for a and b at initial state
but there is no transition at
state
1. This
TG still does not accept any
string. In TG3 there are
transitions at both initial state
and state 1, but it
does
not
accept any string.
Thus none
of TG1, TG2 and
TG3 accepts any
string, i.e.
these TGs
accept empty language. It may be
noted that
TG1 and TG2 are
TGs but not FA, while TG3 is both TG and FA as
well.
It may be
noted that every FA is a TG as
well, but the converse may
not be true, i.e.
every TG
may not be an
FA.
Example
Consider
the language L of strings,
defined over Σ={a, b},
starting
with b. The
language L may be
expressed
by RE b(a +
b)* , may be accepted
by the following TG
a,b
b
æ
+
23
Theory of
Automata
(CS402)
Example
Consider
the language L of strings,
defined over Σ={a, b},
not
ending in b. The
language L may be
expressed
by RE Λ + (a +
b)*a , may be
accepted by the following
TG
a,b
a
+
Λ
+
Example
Consider
the Language L of strings, defined
over Σ = {a, b}, containing
double a.
The
language L may be expressed by
the following regular
expression (a+b)* (aa)
(a+b)*. This language
may be
accepted
by the following TG
b,a
b,a
aa
2+
1-
Example
Consider
the language L of strings,
defined over Σ={a, b},
having
double a or double b.
The
language L can be expressed by RE
(a+b)* (aa + bb)
(a+b)*.
The
above language may also be
expressed by the following
TGs.
x
a
a
a,b
a,b
+
b
b
y
OR
a,b
a,b
aa,bb
-
+
OR
a,b
a,b
aa
2+
1-
a,b
a,b
bb
4+
3-
Note
In the
above TG if the states are
not labeled then it may not be
considered to be a single TG
24
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