Information Technology Reference
In-Depth Information
E
J
(w)
=
E
J
∩
Sub(w),
while the set of left and right elementary cables occurring in
w
is
L
J
(w)
=
L
J
∩
Pref (w)
=
R
J
∩
R
J
(w)
Suff (w),
respectively, where
Pref (w)
,
Suff (w)
,
Sub(w)
denote the set of all prefixes,
suffixes and respectively subwords of
w
.
One can prove that recombination of cables does not produce additional ele-
mentary cables [6]. In other words, the set of the elementary cables of the result
strings equals the set of elementary cables of the strings entering recombination.
A
context-free recombination system
is a construct whereby we are given
a starting set of sequences and a list of pointers (plugs). New strings may
be formed by recombinations among the existing strands: if given pointers are
present, recombinations are performed as defined. Recombinations are context-
free (i.e., they are not dependent on the context in which the pointers appear).
The language of the system is defined as the set of all strands that can be thus
obtained by repeated recombinations starting from the initial set.
DEFINITION 4
A context-free recombination system is a triple
R
=
(
Σ
,J,A),
⊆ Σ
+
is a set of plugs, while
A
⊆ Σ
+
∪ Σ
•
is
where
Σ
is an alphabet and
J
the set of axioms of the system.
The theorem below shows that a context-free recombination system charac-
terized by a set of plugs
J
and a set of axioms
A
has the following property:
any cable that consists of elementary cables plugged together after each other
and that is either linear or circular can be obtained from the axioms using
cross-plugging. Conversely, no other types of cables can be obtained from the
axioms.
THEOREM 1
,J,A)
be a context-free recombination system. Then
L(R)
=
X
where
X
={
w
∈ Σ
∗
∪ Σ
•
|
Let
R
=
(
Σ
either
E
J
(w)
=
L
J
(w)
=
R
J
(w)
=∅
and
w
∈
A
or
E
J
(w), L
J
(w), R
J
(w)
are not all empty and
E
J
(w)
⊆
E
J
(A)
,
L
J
(w)
⊆
L
J
(A)
,
L
J
(w)
⊆
L
J
(A)
}
.
The theorem above will lead to the conclusion of this section provided we
show that the language
X
is regular being accepted by a finite automaton. As
X
contains both linear and circular words, we have to first define the notion of
acceptance of circular words by a finite automaton.
DEFINITION 5 Given a finite automaton
A
, the circular language accepted by
A
, denoted by
L(
A
)
•
, is defined as the set of all words
•
w
such that
A
has a
cycle labeled by
w
.
