ZeePedia buy college essays online


Theory of Automata

<<< Previous Examples of TGs: accepting all strings Next >>>
 
img
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
img
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