Hardware Reference
In-Depth Information
a
b
c
a
a
a
b
b
b
Fig. 4.1
(
a
) Automaton
A
1
;(
b
) Automaton
A
2
; Automaton
A
3
a
b
b
b
a, b
a
b
b
a
Fig. 4.2
(
a
) Non-deterministic automaton
A
1
;(
b
) deterministic automaton
A
2
fin
.
A
3
/
Df
a.ba/
?
g
. Notice that
L
!
-regular languages, as
?
-regular languages, can
L
!
.
A
3
/
Df
.ab/
!
gDf
a.ba/
!
g
.
2
be denoted by different expressions, e.g.,
Example 4.6.
The equality of prefixes of
!
-languages does not imply the equality
-languages, nor vice versa, as the following examples show.
3
of
!
L
1
D
L
2
.L
1
/
D
.L
2
/
•From
, it does not follow
Pref
Pref
, i.e., the equality of
!
-languages does not imply the equality of prefixes. E.g., given two empty
!
-
L
1
L
2
.L
1
/
Df
ab
g
,
Pref
.L
2
/
Df
ba
g
and so
languages
and
, it may be that
Pref
.L
1
/
¤
Pref
.L
2
/
L
1
D
L
2
D;
?
Pref
. Question: does this happen only when
.L
1
/
D
.L
2
/
L
1
D
L
2
•From
Pref
Pref
, it does not follow
, i.e., the equality of
L
1
D
prefixes does not imply the equality of
!
-languages. E.g.,
˙
Df
a;b
g
,
˙
?
a˙
!
,
L
2
D
˙
?
a˙
!
[
b
!
,
Pref
.L
1
/
D
Pref
.L
2
/
L
1
¤
L
2
,but
.
.L
1
/
D
Pref
.L
2
/
D
a
?
b
?
,and
L
1
D
a
?
b
!
,
L
2
D
Another example, is
Pref
a
!
C
a
?
b
!
.
A
1
in Fig.
4.2
a.
4
Example 4.7.
Consider the
non-deterministic
automaton
The language of
A
1
when interpreted as an automaton over finite words is
fin
L
.
A
1
/
Df
w
W
w
ends with
b
g
, whereas its language when interpreted over infinite
L
!
.
A
1
/
Df
w
W
a
words is
occurs a finite number of times in
w
g
.
For languages over finite words, we know that non-deterministic automata and
deterministic automata are equivalent. Hence, consider the following
deterministic
automaton
A
2
in Fig.
4.2
b.
A
2
is obtained by determinization of the automaton
A
1
, by applying the classic
subset construction introduced for automata over finite words. Therefore
A
2
when
interpreted as an automaton over finite words recognizes the same language as
A
1
:
2
We thank V. Bushkov, University of Tomsk, for discussions on Example
4.5
.
3
We thank A. Chebotarev, Ukrainian Academy of Sciences, Kiev, for discussions on Example
4.6
.
4
We thank D. Bresolin, University of Verona, for discussions on Example
4.7
.
Search WWH ::
Custom Search