Основные понятия и определения. Теория автоматов Часть 2

Теория автоматов Часть 2.

Формальные грамматики и языки. Применение.

Основные понятия и определения

Теория формальных грамматик (ФГ) дает:

- способы задания входных данных;

- способы задания и генерации выходных данных;

- способы задания функции, алгоритма преобразования входных данных в выходные;

- способы анализа входных данных

и др.

Основное применение ФГ:

- разработка собственных компиляторов;

- разработка переводчиков;

- преобразование строк, массивов;

- разработка поисковых запросов.

Опр. Алфавит V - конечное непустое множество элементов, называемых символами (буквами).

Опр. Цепочкой a в алфавите V называется любая конечная последовательность символов этого алфавита.

Пример. Пусть алфавит V = {a,b,c}. Тогда baaa является словом в алфавите V.

Опр. Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается e(l).

Опр. Длиной цепочки w называется число составляющих ее символов (обозначается | w |), причём каждый символ считается столько раз, сколько раз он встречается в w.

Пример. Очевидно, |baaa| = 4 и | e | = 0.

Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e, а через V + - множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e.

Пример. Пусть V = {1,0}, тогда V* = {e,0,l,00,01,10,11,000,...},

а V+ ={0,1,00,01,10,11,000,...}.

Опр. Если х и у - слова в алфавите V, то слово ху (результат приписывания слова у в конец слова х) называется конкатенацией (катенацией, сцеплением) слов х и у. Иногда конкатенацию слов х и у обозначают х × у.

Опр. Если х - слово и п Î N, то через х^п обозначается слово х × х ×. .. × x. По определению х⁰ = e.

Пример. ba³ = bааа и (ba)³ = bababa.

Опр. Говорят, что слово х - префикс (начало) слова у, если у = хи.

Опр. Говорят, что слово х - суффикс (конец) слова у, если у = их.

Опр. Говорят, что слово х — подслово слова у, если у = uxv для некоторых слов и и v.

Опр. Через |w|a обозначается количество вхождений символа а в слово w.

Пример. Если V = {a,b,c}, то |baaa| а = 3, |baaa| b = 1 и |baaa| c = 0.

Опр. Формальный язык – это множество конечных слов (строк, цепочек) над конечным алфавитом V.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения, разности и дополнения языков, заданных над одним и тем же алфавитом (обозначения L1 È L2, L1 Ç L2, L1 — L2).

Пример. Множество {a, abb} является языком над алфавитом { a,b }.

Пример. Множество {a^kba^l | k ≤ l } является языком над алфавитом {a,b}.

Необходимо различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={e}≠0.

Опр. Пусть L – язык над алфавитом V*. Тогда язык V* — L называется дополнением языка L относительно алфавита V. Когда из контекста ясно, о каком алфавите идёт речь, говорят просто, что язык V* — L является дополнением языка L.

Опр. Грамматика – система правил, предназначенная для задания множества цепочек и символов данного алфавита. G – грамматика; L(G) – язык этой грамматики.

Выделяют 3 группы формальных грамматик:

1. Порождающие (позволяют строить правильную цепочку в заданном алфавите с описанием ее строения и не позволяют строить ни одной неправильной цепочки).

2. Распознающие (позволяют определить к каждой входной цепочке: является ли она правильной; в случае положительного ответа распознающая ФГ выдает строение цепочки).

3. Преобразующие (для каждой правильно построенной цепочки способны построить ее отображение в виде другой цепочки и вывести информацию о порядке проведения изображения).