(i) L
a b
n
m
nm
n m
1
1
1
3
=
≥
≥
≥
{
:
,
,
}
(ii) L
ab w n
w a b
n
2
3
=
≥
∈
+
{
:
,
{ , } }
(iii) L
vwv v w a b v
3
2
=
∈
=
{
: ,
{ , } , | | }
*
(iv) L
w w
4
3 0
=
=
{ : | | mod
}
Solu tion:
(i) Regular Expression for L
a b
n
m
nm
n m
1
1
1
3
=
≥
≥
≥
{
:
,
,
} is given
by
aa (a
* ) b(b
* ) + a(a
* ) bb (b
* )
(ii) Regular Expression for L
ab w n
w a b
n
2
3
=
≥
∈
+
{
:
,
{ , } } is given
by
abbb (b
* ) (a + b) (a + b)
*
(iii) Regular Expression for L
vwv v w a b
v
3
2
=
∈
=
{
: ,
{ , } , | | }
*
is given
by
(a + b) (a + b) (a + b)
* (a + b) (a + b)
(iv) The regular expression for L
w w
4
3 0
=
=
{ : | | mod
} is given by
(aaa + bbb + ccc + aab + aba + abb + bab
+ bba + cab + cba + cbb + caa)
*
1.5 TWO-WAY FINITE AUTOMATA
Two-way finite automata are machines that can read input string in either
direction. This type of machines have a “read head”, which can move left or
right over the input string.
Like the finite automata, the two-way finite automata also have a finite set
Q of states and they can be either deterministic (2DFA) or nondeterministic
(2NFA).
They accept only regular sets like the ordinary finite automata. Let us
assume that the symbols of the input string are occupying cells of a finite tape,
one symbol per cell as shown in fig. The left and right endmarkers |— and —|
enclose the input string. The endmarkers are not included in the input alphabet
Σ.
|— a 1 a 2 a 3 …… a n —|
Q
88
Theory of Automata, Formal Languages and Computation