2014-02-02
2803
Класс контекстно-свободных языков замкнут относительно объединения и не замкнут относительно пересечения и дополнения. Это говорит о том, что теоретико-множественные операции, за исключением объединения, не имеют естественной синтаксической интерпретации. С этой точки зрения большой интерес представляют операции, связанные с подстановками языка в язык [ 3 ].
Пусть L0 - язык, заданный грамматикой:
G0 = {V0, W0, R0, I 0}, a Î V0;
L1 - язык, заданный грамматикой G1 = {V1, W1, R1, I1}.
Определение. Подстановка языка L1 в язык L0 вместо символа a - это операция, сопоставляющая языкам L0 и L1 язык L = L0 (a ® L1), состоящий из всех цепочек L0, в которых вместо символа a подставлена некоторая цепочка из L1.
Обобщением рассмотренной подстановки является подстановка
L = L0 (a1 ® L1,..., ak ® Lk) нескольких языков.
Пример. Пусть заданы языки вида:
L0 = { a, (a + a), (a + a + a),... } L1 = { b, bb, bbb,... }
требуется выполнить подстановку L1 в L0.
Решение. Подстановка L1 в L0 будет иметь вид:
L = L0 (a ® L1) = L = { b, bb, bbb,...,(b + b), (bb + b),...}.
Определение. Конкатенация языков L0 и L1 - эта операция
|
|
|
L0L1, сопоставляющая языкам L0 и L1 язык L, содержащий цепочки, представляющие собой парное сцепление цепочек языков L0 и L1.
Пример. Пусть заданы языки вида:
L0 = { a, (a+a), (a+a+a),... } L1 = { b, bb, bbb,... }
требуется выполнить конкатенацию L1 и L0.
Решение. Конкатенация L1 и L0 будет иметь вид:
L = L0L1 = { ab, abb, abbb, (a+a)b,...}.
Введем в рассмотрение степенные обозначения конкатенаций
LL=L2, LLL=L3,....
Подстановки будем обозначать следующим образом:
Определение. Итерацией L* языка L называется язык вида:
L* = { e } È L È L2 È... È Ln ,
где { e } - пустая цепочка.
Замечание. Не следует путать язык, содержащий одну пустую цепочку, с пустым языком, не содержащим ни одной цепочки, так как
L {e} = {e} L = L, а LÆ = Æ для любого L.
