Hardware Reference
In-Depth Information
Quantifiers:
In mathematical logic, there are two quantifiers: a
universal quantifier
8
and an
existential quantifier
9
.IfP.x/ is a formula dependent on some variable x
then
8
xP.x/is true iff P.x/ is true for all values of x.
9
xP.x/is true iff P.x/ is
true for some value of x. Of course, the result of the quantification depends on the
variable domain.
Example 21.3.
Suppose that the domain of x is the set of integers. The formula
8
x
9
yx
D
2y is true if the domain of y is the set of real or rational numbers, but it
is false if the domain of y is the set of integers or natural numbers.
t
21.1.3
Languages
We call a finite set ˙
Df
1
;:::;
k
g
an
alphabet
, and its elements
1
;:::;
k
letters
. Any sequence of letters is called a
word
,ora
trace
, and we use these terms
interchangeably. If the word does not contain any letters, it is called the
empty word
and is denoted ". We distinguish between
finite
and
infinite
words (traces).
Any set L of words is called a
language
. If all the words of the language are
finite, the language is called
finitary
, if all the words of the language are infinite, the
language is called
infinitary
.
Example 21.4.
The words of written English form a finitary language according to
our definition. Its alphabet consists of 26 Latin letters “a” through “z”,
1
and for
every sequence of Latin letters we can say whether it is an English word or not. For
example,
building
is an English word, whereas
buildign
is not.
t
21.1.4
Finite Automaton
A
finite automaton
is a tuple
h
˙; S; S
0
;;F
i
, where ˙ is an alphabet, S
D
f
s
1
;:::;s
n
g
is a finite set of
states
, S
0
S is the set of initial states,
S
˙
S
is the
transition relation
, and F
S is the set of the
accepting states
.
It is convenient to represent a finite automaton as a directed graph in which
vertices are automaton states and edges are labeled with the alphabet letters to
represent the transition relation. If s
i
;s
j
2
S and
2
˙ , then there is a labeled
edge s
i
A
!
s
j
in the graph iff .s
i
;;s
j
/
2
. We mark the initial states with a double
incoming arrow and the final states with a double circle.
1
For our purpose, there is no need to distinguish between small and capital letters. We also ignore
the fact that there exist words with spaces, hyphens, etc.
Search WWH ::
Custom Search