Теория и реализация языков программирования



Алфавиты, цепочки и языки


Алфавит, или словарь - это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа

 \sharp, \$

Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один символ.

Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x.

Пусть x, y, z - произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки.

Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества

 L_1 = \{e, a, ab, abb, abbb, abbba\}

суффиксом является любая цепочка из множества

 \{e, a, ba, bba, bbba, abbba\}

подцепочкой является любая цепочка из множества

 L_1 \bigcup L_2

Длиной цепочки w (обозначается |w|) называется число символов в ней. Например, |abababa| = 7, а |e| = 0. Язык в алфавите V - это некоторое множество цепочек в алфавите V .

Пример 2.2. Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V:

  1. L_1={\O}
    — пустой язык;
  2. L_2 = \{e\}
    - язык, содержащий только пустую цепочку (заметим, что
    L_1
    и
    L_2
    - различные языки)
  3. L_3
    - язык, содержащий цепочки из a и b, длина которых не превосходит 2
  4. L_4
    - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b
  5. L_5 = \{a^{n^2}|n>0\}
    - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.

Два последних языка содержат бесконечное число цепочек.

Введем обозначение

V^*
для множества всех цепочек в алфавите
V^*
, включая пустую цепочку. Каждый язык в алфавите V является подмножеством
V^*
. Для обозначения множества всех цепочек в алфавите V , кроме пустой цепочки, будем использовать
V^+
.

Пример 2.3. Пусть

V=\{0,1\}
. Тогда
V^*=\{e, 0, 1, 00, 01, 10, 11, 000, \ldots\}, V^+=\{0, 1, 00, 01, 10, 11, 000, \ldots\}

Введем некоторые операции над языками.

Пусть

L_1
и
L_2
- языки в алфавите V .


Содержание    Вперед