Hardware Reference
In-Depth Information
If
C
˘
!E
L.
A
C
˘
!H
A
S
/
D
S
,then
L.
A
C
˘
!H
A
S
/
is the largest solution of
the equation
C
˘
!E
X
D
S
.
We will describe in Chap. 18 an heuristic algorithm to solve synchronous
equations over
!
-languages represented by Buchi automata.
Problems
4.1.
Show that the set of finite subsets of natural numbers,
!
Df
0;1;2;:::
g
,
represented as a set of strings in
f
0;1
g
!
, is accepted by a non-deterministic Buchi
automaton, but by no deterministic Buchi automaton (from [73]).
Notice that a set
A
!
is represented by its characteristic string, i.e., the infinite
string over
f
0;1
g
with a
1
in position
i
if and only if
i
2
A
. For example the
characteristic string of the set of multiples of 3 is:
100100100100100100100100:::
the characteristic string of primes is:
001101010001010001010:::
the characteristic set of singleton 4 is:
000010000000000000000:::
4.2.
Show that every set accepted by a Buchi automaton is a finite union of sets of
the form
AB
!
,where
A
and
B
are regular sets.
4.3.
Consider the automaton in Fig.
4.4
.
(a) What is its language when interpreted as a finite automaton?
(b) What is its language when interpreted as a Buchi automaton, with
A
as the final
state?
(c) Is there a deterministic Buchi automaton to recognize the complement of the
language defined in (b)?
(d) What is its language when interpreted as a co-Buchi automaton, with
B
as the
persistent state?
a
b
a
Fig. 4.4
(
a
)Buchi
automaton for Problem
4.3
B
A
b
Search WWH ::
Custom Search