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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
слов русского языка, которые можно разыскать в орфографическом словаре. Оче-
видно L
2
⊂ L
1
, так как многие цепочки языка L
1
не являются русскими словами.
Пусть В и С – некоторые подмножества множества А*.
Произведением множеств В и С называется множество D цепочек, являю-
щихся конкатенацией цепочек из В и С, т. е.
D = { X o Y | X ∈ B, Y ∈ C}.
Обозначается произведение следующим образом:
D = ВC.
Рассмотрим алфавит А. Обозначим множество, состоящее из ε, через А
0
. Опре-
делим степень алфавита как А
n
= A
n-1
A для каждого n ≥ 1.
Нетрудно показать, что множество всех возможных цепочек алфавита
А* =
U
∞
=0n
n
А
.
Такое множество называют итерацией алфавита А. Усеченной итерацией ал-
фавита А называют
А
+
=
U
∞
=1n
n
А
.
Если X и Y – цепочки множества А*, то цепочку Х называют подцепочкой це-
почки Y, когда существуют такие цепочки U и V из А*, что
Y = UoXoV.
При этом, если U – пустая цепочка, то подцепочку Х называют головой цепоч-
ки Y, а если V – пустая цепочка, то Х называют хвостом цепочки Y.
Конкатенация двух цепочек X и Y обозначается ХоY или XY.
Рассмотрим пары цепочек (P
1
, Q
1
), (P
2
, Q
2
), ..., (P
n
, Q
n
) из А* х А*.
Соотношениями Туэ будем называть правила, согласно которым любой це-
почке X = U P
i
V из множества А* будет ставиться в соответствие цепочка Y = U Q
i
V,
из того же множества А* (i = 1, 2, ..., n) и наоборот. Эти соотношения приводят к так
называемым ассоциативным исчислениям.
Если цепочка Y получается из цепочки Х однократным применением одного
соотношения Туэ (т. е. заменой подцепочки P
i
на подцепочку Q
i
), будем говорить, что
Х и Y являются смежными цепочками.
Цепочка Х
n
соотносима с цепочкой Х
0
, если существует последовательность
цепочек
Х
0
, Х
1
, ..., Х
n
,
такая, что Х
i-1
и Х
i
являются смежными цепочками.
Пример 2. Пусть А – множество букв русского алфавита, на котором опреде-
лим соотношение Туэ, заключающееся в праве замены любой одной буквы слова на
любую другую. Тогда в последовательности цепочек МУКА, МУЗА, ЛУЗА, ЛОЗА,
ПОЗА, ПОРА, ПОРТ, ТОРТ, две любые соседние цепочки являются смежными, а це-
почки МУКА и ТОРТ являются соотносимыми в смысле заданных соотношений.
Введение соотношений Туэ позволяет выделить среди множества языков опре-
деленные их классы, которые используются при построении автоматно-
лингвистических моделей самого различного типа.
Соотношения Туэ являются двусторонними, если цепочка Х является смежной
по отношению к цепочке Y, и наоборот, цепочка Y является смежной по отношению к

Страницы