Математическая теория формальных языков


Операции над языками - часть 2


Множество Subw(L) называется множеством подслов

языка L.

Определение 1.2.22. Слово a1a2...an

(длины ) называется подпоследовательностью (subsequence) слова y, если существуют такие слова u0, u1, ..., un, что u0a1u1a2...anun = y.

Замечание 1.2.23.

Все подслова слова y являются также подпоследовательностями слова y.

Определение 1.2.24. Пусть . Тогда через Subseq(L) обозначается множество, состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L) называется множеством подпоследовательностей

языка L.

Пример 1.2.25. Рассмотрим язык L = {cba, c} над алфавитом {a, b, c}. Очевидно, что .

Определение 1.2.26. Функция

называется биекцией (bijection), если каждый элемент множества L является образом ровно одного элемента множества K (относительно функции f).

Определение 1.2.27. Множества K и L называются равномощными (of equal cardinality), если существует биекция из K в L.

Упражнение 1.2.28. Существуют ли такие языки L1 и L2, что языки

и неравномощны?

Упражнение 1.2.29. Существуют ли такие языки L1 и L2, что языки

и неравномощны?




Начало  Назад  Вперед



Книжный магазин