Основы конструирования компиляторов



             

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


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

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

символ.

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

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

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

из множества L1 = {e, a, ab, abb, abbb, abbba}, суффиксом является любая цепочка из множества L2 = {e, a, ba, bba, bbba, abbba}, подцепочкой является любая цепочка из множества L1

L2.

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

Язык в алфавите V - это некоторое множество цепочек в алфавите V .

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

  • L1 =
    - пустой язык;
  • L2 = {e} - язык, содержащий только пустую цепочку

    (заметим, что L1 и L2 - различные языки);

  • L3 = {e, a, b, aa, ab, ba, bb} - язык,

    содержащий цепочки из a и b, длина которых не превосходит 2;

  • L4 - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b;
  • L5 = {an2

    |n > 0} - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.

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

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

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


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