ZeePedia buy college essays online


Theory of Automata

<<< Previous FA corresponding to finite languages Next >>>
 
img
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
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
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
img
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
img
Theory of Automata
(CS402)
a
b
4+
2
a
b
a
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