Как называются языки в которых есть алфавит

Как называются языки в которых есть алфавит

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

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

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

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

Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества L 1 = , суффиксом является любая цепочка из множества L 2 = , подцепочкой является любая цепочка из множества L 1 L 2.

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

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

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

  • L 1 = — пустой язык;
  • L 2 = — язык, содержащий только пустую цепочку

(заметим, что L 1 и L 2 — различные языки);

  • L 3 = — язык, содержащий цепочки из a и b, длина которых не превосходит 2;
  • L 4 — язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b;
  • L 5 = 0> — язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.
  • Два последних языка содержат бесконечное число цепочек.

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

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

    Пусть L 1 и L 2 — языки в алфавите V . Конкатенацией языков L 1 и L 2 называется язык L 1L 2 = , y L 2>.

    Пусть L — язык в алфавите V . Итерацией языка L называется язык L * , определяемый следующим образом: