 |
FA corresponding to finite languages |
| << Equivalent FAs |
| Examples of TGs: accepting all strings >> |
Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 7
Reading
Material
Chapter 5,
6
Introduction
to Computer Theory
Summary
FA corresponding to
finite languages(using both methods),
Transition graphs.
FA
corresponding to finite languages
Example
Consider
the language
L = {Λ, b,
ab, bb}, defined
over Σ ={a, b}, expressed by
Λ + b + ab + bb OR Λ + b (Λ + a + b).
The
language L may be accepted by
the FA as shown aside
a,b
y
a
a,b
a
b
4+
3
1±
b
b
5+
2+
It is to be
noted that the states x
and y are called
Dead
States, Waste Baskets or
Davey John Lockers, as
the
a,b
a
moment
one enters these states
there is no way to leave
it.
Note
x
It is to be
noted that to build an FA
accepting the language
having less number
a,b
of
strings, the tree structure
may also help in this regard,
which can be observed
in the
following transition diagram for
the
4
Language
L, discussed in the above
example
a
3
a,b
b
a
a,b
5+
a,b
1±
8
a,b
6
b
a
a,b
2+
a,b
b
7+
x
a,b
b
a
a
Example
a
a
b
3+
b
4
2
Consider
the language
1
5+
L = {aa,
bab, aabb, bbba}, defined
over Σ ={a, b},
b
expressed
by aa + bab + aabb +
bbba
b
b
a
6
9+
8
7
OR aa (Λ +
bb) + b (ab + bba)
a
The
above language may be
accepted by the FA
a
as shown
aside
b
10
a,b
a
b
a,b
y
11+
a,b
20
Theory of
Automata
(CS402)
Example
Consider
the language L = {w belongs to
{a,b}*: length(w) ≥2 and w
neither ends in aa nor
bb}.
The
language L may be expressed by
the regular expression
(a+b)*(ab+ba)
This
language may be accepted by
the following FA
21
Theory of
Automata
(CS402)
a
b
4+
2
a
b
a
1
a
b
b
b
a
5+
3
Note
It is to be
noted that building an FA corresponding
to the language L, discussed in
the above example, seems
to
be quite
difficult, but the same can
be done using tree structure along
with the technique discussed
in the book
Introduction
to Languages and Theory of
Computation, by J. C.
Martin
so that
the strings ending in aa,
ab, ba and bb should end in
the states labeled as aa,
ab, ba and bb,
respectively;
a
as shown in
the following FA
aa
a
a
b
b
a
a
ab
Λ
a
b
ba
b
a
b
a
b
b
b
bb
Example
Consider
the language FA corresponding to r1+r2 can be determined
as
L = {w
belongs to {a,b}*: w
does not end in aa}.
The
language L may be expressed by
the regular expression Λ + a + b +
(a+b)*(ab+ba+bb). This
language may
a
be
accepted by the following
FA
aa
a
a
b
b
a
a
ab
Λ
a
b
ba
b
a
b
b
a
b
b
Method 5
(Transition Graph)
bb
Definition:
A
Transition graph (TG), is a collection of
the followings
Finite
number of states, at least one of
which is start state and
some (maybe none) final
states.
Finite
set of input letters (Σ)
from which input strings
are formed.
Finite
set of transitions that show
how to go from one state to
another based on reading specified substrings
of
input
letters, possibly even the
null string (Λ).
22
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