 |
Finite Automaton |
| << Equivalent Regular Expressions |
| Equivalent FAs >> |
Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 5
Reading
Material
Chapter
5
Introduction
to Computer Theory
Summary
Different
notations of transition diagrams,
languages of strings of even
length, Odd length, starting
with b,
ending in
a, beginning with b, not
beginning with b, beginning
and ending in same
letters
Note
It may be
noted that to indicate the
initial state, an arrow head
can also be placed before
that state and that
the
final
state with double circle, as shown below.
It is also to be noted that
while expressing an FA by its
transition
a,
b
diagram,
the labels of states are not
necessary.
a,
b
Example
Σ =
{a,b}
States:
x, y,
where x is both initial and final
state.
Transitions:
At state
x reading a or b go to state y.
At state
y reading a or b go to state x.
These
transitions can be expressed by
the following transition
table
New
States
Old
States
Reading
Reading
a
b
x±
y
y
y
x
x
It may be
noted that the above
transition table may be depicted by
the following transition diagram.
a,
b
x±
y
a,
b
The
above transition diagram is an FA accepting
the language of strings,
defined over Σ={a, b} of even
length.
It may be
noted that this language
may be expressed by the
regular expression ((a+ b) (a +
b))*
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 FA
a,b
b
+
a,b
a
1
Example
Consider
the language L of strings,
defined over Σ={a, b},
ending in
a. The
language L may be expressed
by
RE
(a+b)*a.
15
Theory of
Automata
(CS402)
b
This
language may be accepted by
the
a
a
FA shown
aside
+
b
a
There
may be another FA
a
+
corresponding to
the given
language,
as shown aside
a
b
b
b
Note
It may be
noted that corresponding to a given
language there may be more
than one FA accepting that
language,
but
for a given FA there is a unique
language accepted by that
FA.
It is
also to be noted that given
the languages L1 and
L2 ,where
L1 = The language of strings,
defined over Σ ={a, b},
beginning
with a.
L2 = The language of strings,
defined over Σ ={a, b},
not
beginning with b
The
Λ
does
not belong to L1
while it
does belong to L2 .
This fact may be depicted by
the corresponding
transition
diagrams of L1
and L2.
a,b
FA1 Corresponding to L1
a
+
a,b
b
The
language L1 may be expressed by
the regular expression a(a +
b)*
FA2 Corresponding to L2
a,b
a
±
+
a,b
b
The
language L2
may be
expressed by the regular
expression a(a + b)* +
Λ
Example
Consider
the Language L of Strings of length
two or more, defined
over Σ = {a, b}, beginning
with and
ending in
same letters.
The
language L may be expressed by
the following regular
expression a(a + b)*a + b(a +
b)*b
It is to be
noted that if the condition
on the length of string is not imposed in
the above language then
the
b
a
strings a
and b will then belong to
the language.
a
This
language L may be accepted by
the FA as shown aside
+
a
b
a
b
b
b
+
a
16
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