ZeePedia buy college essays online


Theory of Automata

<<< Previous Finite Automaton Next >>>
 
img
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
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
img
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