Information Technology Reference
In-Depth Information
of
CF
languages, but their intersection, having pattern
a
n
b
n
c
n
, is not
CF
.Manyim-
portant properties of languages can be algorithmically established. For example, a
language is infinite iff any grammar generating it has an auto-rewriting symbol, that
is, a non-terminal symbol
X
such that
α
⇒
G
β
α
,
β
where
X
occurs in both strings
,
T
∗
.
However, given two grammars
G
1
⇒
G
γ
γ
∈
andsuchthat
X
with
G
2
of type 2, it can be shown that it is im-
possible to have an algorithm which, in general, is able to decide whether
,
L(
G
1
)
⊆
L(
. We mention other two important results about Chomsky hierarchy. The in-
tersection of any language
L
with a regular language preserves the Chomsky type of
L
. Moreover any language
L
of type 0 can be obtained by a suitable
CS
language
L
by deleting a special symbol from all the strings of
L
.
G
2
)
6.4
Patterns and Rules
The notion of string pattern was already introduced in informal way. Here its formal
definition follows.
Definition 6.6.
A string pattern over an alphabet
A
is an algebraic expression
P
built
by means of symbols (of the alphabet), variables (with specified ranges of variabil-
ity), and operations. When variables of
P
are instantiated by values in the respective
ranges, then
P
denotes a string over the alphabet
A
.If
P
=
P
(
x
1
,
x
2
,...,,
x
k
)
is a
pattern of variables
x
1
,
x
2
,...,,
x
k
,and
S
1
,
S
2
,...,,
S
k
are the respective ranges of its
variables, then the language
L(
P
)
defined by
P
is given by:
A
∗
|
α
1
∈
L(
P
)=
{
P
(
x
1
:
=
α
1
,
x
2
:
=
α
2
,...,,
x
k
:
=
α
k
)
∈
S
1
,
α
2
∈
S
2
,...,,
α
k
∈
S
k
}
where
P
(
x
1
:
=
α
,
x
2
:
=
α
,...,,
x
k
:
=
α
k
)
is the evaluation of the pattern when the
1
2
values
,...,
α
k
are assigned to the corresponding variables (and the operations
are applied according to the structure of the expression
P
).
α
,
α
1
2
For example, let us consider the pattern:
x
n
ay
m
bx
n
+
m
A
∗
,
n
with
x
m
(with their
ranges of variability). When variables are instantiated and concatenation, iteration,
and arithmetical sum are applied, we get a string of
A
∗
.
The elements of
,
y
∈
,
m
∈
N
.Herewehavestrings
a
,
b
and variables
x
,
y
,
n
,
are also called
instances
of the pattern. In more complex
cases, specific constraints can be required to a pattern (for example, the number of
its variables). Patterns can be combined by using the language operations
L(
P
)
.
In fact, if
P
1
and
P
2
are two patterns that identify languages, then, in a completely
natural way,
P
1
+
+
,·,/,∩
P
2
means that:
L(
P
1
+
P
2
)=L(
P
1
)+L(
P
2
)
and analogously for concatenation, difference, intersection, and Kleene star.
