Синтез цифровых автоматов. Захаров Н.Г - 130 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

129
Пусть В и С – некоторые подмножества множества V*, а V
1
и V
2
– цепочки
этого множества V*.
Произведением множеств В и С (не путать с декартовым произведением, эле-
ментами которого в данном случае были бы не цепочки, а упорядоченные пары цепо-
чек. Обозначается ×, см. далее в п. 3) называется множество D цепочек, являющихся
конкатенацией (слиянием) цепочек из В и С, т. е.
D = BC = {V
1
V
2
| V
1
∈ B, V
2
∈ C}.
Итерацией алфавита V называют множество всех цепочек алфавита
V* =
U
∞
=0n
n
V
,
где V* – множество всех цепочек над алфавитом V, включая пустую цепочку
ε;
V
n
– степень алфавита, определяемая как V
n
= V
n-1
V, для каждого n ≥ 1, если
множество, состоящее из пустой цепочки
ε, обозначить через V
0
.
Усеченной итерацией алфавита V называют
V
+
=
U
∞
=1n
n
V ,
где V
+
– множество всех цепочек над алфавитом V, без пустой цепочки ε.
Ассоциативные исчисления
Пусть даны пары цепочек (P
1
, Q
1
), (P
2
, Q
2
), ..., (P
n
, Q
n
) из V*× V*. Если V
1
и V
2
–
цепочки множества V*, то цепочку V
1
называют подцепочкой цепочки V
2
, когда су-
ществуют такие цепочки Х и Y из V*, что V
2
= X V
1
Y.
Соотношения Туэ. Соотношениями Туэ называют правила, согласно которым
любой цепочке
V
1
= XP
i
Y из множества V* будет ставиться в соответствие цепочка
V
2
= XQ
i
Y из того же множества V* (i = 1, 2, ..., n). Такие соотношения и приводят к
так называемым ассоциативным исчислениям.
Направление и порождение. Соотношения Туэ являются двусторонними, если
цепочка V
1
является смежной по отношению к цепочке V
2
, и наоборот, цепочка V
2
является смежной по отношению к цепочке V
1
. Однако бывают соотношения, в кото-
рых вводится
направление.
Соотношения, содержащие направление, называют
полусоотношениями Туэ
или
продукциями и обозначают: (P
1
→ Q
1
), (P
2
→ Q
2
), ..., (P
n
→ Q
n
). Например, если
имеется набор продукций цепочек V
1
и V
2
, то говорят, что V
1
порождает V
2
, или го-
ворят, что цепочка V
2
непосредственно порождается из цепочки V
1
, и обозначается
это как
V
1
⇒ V
2
,
при условии существования таких цепочек Х и Y, что V
1
= XP
i
Y , V
2
= XQ
i
Y, а
(P
i
→ Q
i
) – продукция из данного набора.
Правило. Правило (или продукция) – это упорядоченная пара цепочек символов
(
α, β). В правилах очень важен порядок цепочек, поэтому их часто записывают в виде
α → β. Такая запись читается как «α порождает β» или «β по определению есть α».
Например, Р – множество правил (продукций) грамматики вида
α → β, где
α∈V
+
, β ∈ V*.

Страницы