Математическая теория формальных языков
Операции над языками
Определение 1.2.1.
Пусть . Тогда
Язык
называется конкатенацией
языков L1 и L2.
Пример 1.2.2. Если L1 = {a,abb} и L2 = {bbc,c}, то .
Упражнение 1.2.3. При каких положительных целых числах k, l, m, n существуют алфавит , язык
и язык , удовлетворяющие условиям , |L1| = l, |L2| = m,
Определение 1.2.4. Пусть . Тогда
Пример 1.2.5. Если L = {akbal | 0 < k < l}, то L2 = {akbalbam | 0 < k < l - 1, m > 1}.
Упражнение 1.2.6. Пусть
и L = {aa,ab}. Найти L3.
Определение 1.2.7. Итерацией языка (Kleene closure) языка L (обозначение L*) называется язык
Эта операция называется также звездочкой Клини
(Kleene star, star operation).
Пример 1.2.8.
Если
и L = \{aa,ab,ba,bb}, то
Упражнение 1.2.9. Пусть
и
Верно ли, что
Упражнение 1.2.10. Существует ли такой язык L, что выполняется неравенство
Определение 1.2.11. Обращением или зеркальным образом слова w (обозначается wR) называется слово, в котором символы, составляющие слово w, идут в обратном порядке.
Пример 1.2.12.
Если w = baaca, то wR = acaab.
Определение 1.2.13. Пусть . Тогда
Язык LR
называется обращением
языка L.
Упражнение 1.2.14. Существует ли такой язык L, что выполняется неравенство ?
Определение 1.2.15. Говорят, что слово x - префикс (Содержание) слова y (обозначение ), если y = xu для некоторого слова u.
Пример 1.2.16. Очевидно, что , ,
и .
Определение 1.2.17. Пусть . Тогда через Pref(L) обозначается множество, состоящее из всех префиксов слов языка L:
Множество Pref(L) называется множеством префиксов
языка L.
Определение 1.2.18 Говорят, что слово x - суффикс (конец) слова y (обозначение ), если y = ux для некоторого слова u.
Определение 1.2.19. Пусть . Тогда через Suf(L) обозначается множество, состоящее из всех суффиксов слов языка L:
Множество Suf(L) называется множеством суффиксов
языка L.
Определение 1.2.20. Говорят, что слово x - подслово (substring) слова y, если y = uxv для некоторых слов u и v.
Определение 1.2.21. Пусть . Тогда через Subw(L) обозначается множество, состоящее из всех подслов слов языка L.
Множество 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, что языки
и неравномощны?
