Hardware Reference
In-Depth Information
2.1.3
Classes of Languages
We introduce several classes of languages used later in the paper.
Definition 2.1.4.
A language L over alphabet X is
prefix-closed
if
8
˛
2
X
?
8
x
2
XŒ˛x
2
L
)
˛
2
L: Equivalently, L is prefix-closed iff L
D
Pref
.L/.
Definition 2.1.5.
A language L over alphabet X
D
I
O is I
-progressive
if
8
i
2
I
9
o
2
OŒ˛
2
L
)
˛.i;o/
2
L:
If L is not I -progressive, then
Prog
.L/ is the
largest
I
-progressive language
L
0
such that L
0
L.
D
I
?
.
Definition 2.1.6.
A language L over alphabet I
O is I
#
-defined
if L
#
I
If a language over X
D
I
O is I -progressive it is also I
#
-defined, but the
converse does not hold.
Df
C
i
1
o
1
C
i
1
o
2
.i
1
o
1
/
?
Example 2.8.
The language L
g
is I
#
-defined, but not
I -progressive, as witnessed by ˛
D
i
1
o
1
2
L and i
D
i
1
for which there is no o
such that ˛i
1
o
2
L.
O is
Moore
2
Definition 2.1.7.
A language L over alphabet X
D
I
with respect
to alphabet I ,if
8
.i
0
;o
0
/
2
XŒ˛.i;o/
2
L
)
Œ˛ .i
0
;o
0
/
2
L
)
˛.i
0
;o/
2
L:
8
˛
2
L
8
.i; o/
2
X
Definition 2.1.8.
A language L
.
IO
/
?
over alphabet I
[
O (I and O disjoint) is
IO
-prefix-closed
if
8
˛
2
.
IO
/
?
8
io
2
IO
Œ˛ i o
2
L
)
˛
2
L:
Definition 2.1.9.
A language L
.
IO
/
?
over alphabet I
[
O (I and O disjoint) is
IO
-progressive
if
8
i
2
I
9
o
2
OŒ˛
2
L
)
˛
io
2
L:
Definition 2.1.10.
A language L
.
IU
?
O/
?
over alphabet I
[
U
[
O (I , U and
O pairwise disjoint) is
IU
?
O
-progressive
if
9
ˇ
2
U
?
8
i
2
I
9
o
2
OŒ˛
2
L
)
˛iˇo
2
L:
2
This definition is an abstraction to languages of the most common definition of Moore au-
tomata/finite state machines.
Search WWH ::
Custom Search