Hardware Reference
In-Depth Information
a
c
c
a
a
a
b
b
c
c
c
b
c
a
b
a
b
b
b
a
a
Fig. 4.3
(
a
) Automaton
A
;(
b
) Automaton
.
A
/
*
!B
4.2.4.2
!
-Restriction of
!
-Automata
Proposition 4.20.
GivenaBuchi automaton
A
D
.Q;A
[
B;;q
0
;F/
accepting a
given
!
-regular language
L
over the alphabet
A
[
B
, consider the B uchi automaton
.s;b;s
0
/
A
+
!A
, derived from
A
by replacing every transition
where
s
2
Q
and
.s;;s
0
/
b
2
B
n
A
by the transition
, and then taking its
-closure.
Then
A
+
!A
accepts the
A
-restriction
L
+
!A
of the language
L
accepted by
A
.
4.2.4.3
!
-Product of
!
-Automata
Proposition 4.21.
Given
two
B uchi
automata
A
1
D
.Q
1
;A;
1
;q
01
;F
1
/
and
A
2
D
.Q
2
;A;
2
;q
02
;F
2
/
accepting respectively the given
!
-regular languages
L
1
and
L
2
over the alphabet
A
, consider the B uchi automaton
A
1
\
!
A
2
D
..Q
\
;A;
\
;q
0
\
;F
\
//;
defined as follows:
Q
\
D
Q
1
Q
2
f
1;2
gI
q
0
\
D
.q
01
;q
02
;1/
I
F
\
D
Q
1
Q
2
f
2
gI
\
is such that
..s
1
;s
2
;1/;a;.s
0
1
;s
0
2
;1//
2
\
iff
.s
1
;a;s
0
1
/
2
1
;.s
2
;a;s
0
2
/
2
2
;s
1
62
F
1
,
..s
1
;s
2
;1/;a;.s
0
1
;s
0
2
;2//
2
\
iff
.s
1
;a;s
0
1
/
2
1
;.s
2
;a;s
0
2
/
2
2
;s
1
2
F
1
,
..s
1
;s
2
;2/;a;.s
0
1
;s
0
2
;2//
2
\
iff
.s
1
;a;s
0
1
/
2
1
;.s
2
;a;s
0
2
/
2
2
;s
2
62
F
2
,
..s
1
;s
2
;2/;a;.s
0
1
;s
0
2
;1//
2
\
iff
.s
1
;a;s
0
1
/
2
1
;.s
2
;a;s
0
2
/
2
2
;s
2
2
F
2
.
Search WWH ::
Custom Search