2.5.2. Алфавит, слово, язык

Рассмотрим самое простое понятие теории языков — понятие алфавита.

Алфавит — это произвольное непустое конечное множество , элементы которого называют буквами или символами. Обычно задают определенную нумерацию алфавита (как, скажем, для русского алфавита: „а» — первая буква, „б» — вторая и т.д. до 33-й — „я»). Впредь договоримся, фиксируя алфавит, записывать его буквы в порядке их номеров.

Определение: Словом или цепочкой в алфавите V называют произвольный кортеж из множества (k-й декартовой степени алфавита V) для различных k = 0,1,2,…

Например, если V={а,b,с}, то (а), (b), (с), (а, b), (а, b, с),

(с, b, а, а, с) и т.д. есть слова в V.

При k = 0 получаем пустой кортеж, называемый в данном контексте пустым словом или пустой цепочкой и обозначаемый . Множество всех слов в алфавите V обозначают , а множество всех непустых слов в V — как . Слова, ради удобства чтения и простоты записи, будем записывать без скобок и запятых. Так, для записанных выше слов получим: а, b, с, аb, аbс, сbаас.

Такая запись слова согласуется с его интуитивным пониманием как цепочки следующих друг за другом символов. Тогда пустое слово — это слово, не имеющее символов, „пустой лист бумаги», на котором еще ничего не написано.

По определению, длина слова v — число компонент кортежа, т.е. если то длина слова равна r. Длину слова договоримся обозначать | |. Ясно, что для пустого слова | | = 0. Длину слова тем самым можно понимать как число составляющих это слово букв.

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

В данной нумерации пустому слову присваивается номер 0, а буквам алфавита V — номера 1, …, n соответственно. Если слово х имеет лексикографический номер , то слову присваивается номер . Отсюда следует, что лексикографический номер слова будет равен

Заметим, что последняя сумма напоминает запись числа в системе счисления по модулю n (мощности алфавита) с тем лишь различием, что используется цифра n, но не допускается цифра 0. Итак, по любому слову в алфавите V однозначно вычисляется его лексикографический номер. Обратно, любое натуральное число однозначно раскладывается по степеням п указанным выше образом.

Действительно, если дано число N, то при оно служит номером пустого слова (N = 0) или некоторой буквы алфавита. Иначе представим N в виде

где .

Если , то N есть номер слова . Иначе раскладываем в виде

где . Тогда

С числом поступаем точно так же, как и с . После конечного числа шагов получим разложение числа N в виде

где каждое число находится в диапазоне от 1 до n.

По полученному разложению N однозначно восстанавливается слово в V, имеющее номер N:

2.5.3. Классификация грамматик и языков

Единственное ограничение, накладываемое на правило вывода любой грамматики, состоит в том, что в левую часть правила должен входить хотя бы один нетерминал. В зависимости от дополнительных ограничений, накладываемых на правила вывода грамматики, различают следующие основные классы грамматик.

1. Грамматики типа 0, или грамматики общего вида. Здесь на правила вывода не накладывается никаких дополнительных ограничений.

2. Неукорачивающие грамматики. Каждое правило такой грамматики имеет вид , где . Таким образом, длина правой части правила не меньше длины левой.

3. Контекстно-зависимые грамматики (К3-грамматики). Грамматику называют контекстно-зависимой грамматикой (КЗ-грамматикой), если любое ее правило вывода имеет вид , где А — нетерминал, — некоторая цепочка, . Каждое такое правило, называемое КЗ-правилом, позволяет заменить нетерминал А в „контексте», образуемом цепочками и в объединенном алфавите, непустой цепочкой . Иногда цепочку называют левым контекстом, а цепочку — правым контекстом данного КЗ-правила. Из определения видно, что каждая КЗ-грамматика является неукорачивающей.

Если в КЗ-правиле снять требование непустоты цепочки , то получим грамматику, которую называют обобщенной КЗ-грамматикой (или, коротко, ОКЗ-грамматикой).

4. Контекстно-свободные грамматики (КС-грамматики). Каждое правило такой грамматики имеет вид , т.е. левая часть каждого правила вывода есть нетерминал, а правая — произвольная (может быть и пустая) цепочка в объединенном алфавите. С практической точки зрения это наиболее важный класс грамматик, поскольку именно в терминах КС-грамматик описывается синтаксис языков программирования.

5. Линейные грамматики. Каждое правило такой грамматики имеет вид или т.е. в правой части правила может содержаться не более одного вхождения нетерминала. Если во всех правилах вида имеет место , то грамматика называется праволинейной, а если —леволинейной.