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


Операции над языками


Определение 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.


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



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