- •Глава 2. Способы задания языков
- •2.1. Грамматики.
- •2.1.1. Основные понятия и обозначения.
- •2.1.2. Классификация грамматик по Хомскому.
- •2.2. Распознаватели.
- •Глава 3. Регулярные языки
- •3.1. Праволинейные грамматики
- •3.2. Конечные автоматы
- •Глава 4. Контекстно-свободные языки
- •4.1. Деревья выводов
- •4.2. Нормальная форма Хомского
- •4.3. Нормальная форма Грейбах
- •Глава 5. Автоматы с магазинной памятью
- •5.1. Детерминированный магазинный автомат
- •6. Приемы построения грамматик
- •Sa b c.
2.2. Распознаватели.
Язык можно задать конечными средствами, используя распознаватели. Распознаватель – это алгоритм, определяющий некоторое множество. Распознаватель состоит из следующих частей: входной ленты, входной головки, управляющего устройства с конечной памятью и рабочей памяти. Входная лента – это линейная последовательность ячеек, каждая из которых содержит ровно один символ. Входная головка в данный момент обозревает ровно одну ячейку входной ленты. За один шаг работы распознавателя входная головка может выполнить одно из следующих действий: сдвинуться на одну ячейку влево, сдвинуться на одну ячейку вправо, остаться на месте. В процессе работы распознавателя входная головка читает или пишет символы на входную ленту. Рабочая память в распознавателях, если она есть, организована как магазинная или списковая. Управляющее устройство представляет собой конечное множество состояний вместе с отображением, описывающим изменение состояний в зависимости от текущего входного символа и текущего состояния памяти. Управляющее устройство определяет направление движения входной головки и записываемые в рабочую память данные.
Работа распознавателя складывается из последовательности шагов или тактов. За один такт выполняются следующие действия:
входная головка сдвигается на одну ячейку влево, или на одну ячейку вправо, или остается на месте;
в рабочую память записываются некоторые данные;
изменяется состояние управляющего устройства.
Поведение распознавателя описывают в терминах конфигураций. В конфигурацию объединена следующая одномоментная информация о распознавателе:
состояние управляющего устройства;
содержимое входной ленты и положение входной головки;
содержимое памяти.
Конфигурация называется начальной, если управляющее устройство находится в заданном начальном состоянии, входная головка обозревает самый левый символ на входной ленте, память имеет начальное содержание.
Конфигурация называется заключительной, если управляющее устройство находится в одном из заранее определенных заключительных состояний, входная лента прочитана вся. Иногда в заключительной конфигурации накладывают некоторые ограничения на состояние памяти.
Распознаватель допускает входную цепочку, если, начиная с начальной конфигурации, в которой входная цепочка записана на входной ленте, распознаватель может, выполнив конечное число тактов, попасть в заключительное состояние.
Каждому классу грамматик из иерархии Хомского соответствует класс распознавателей, задающий тот же класс языков. Такими распознавателями являются конечные автоматы, автоматы с магазинной памятью, линейно-ограниченные автоматы и машины Тьюринга.
Глава 3. Регулярные языки
3.1. Праволинейные грамматики
Регулярные (автоматные) грамматики относятся к наиболее простому типу грамматик. Различают регулярные грамматики с левосторонними продукциями вида
A → Bx или A → x,
и регулярные грамматики с правосторонними продукциями вида
A → xB, или A → x, где A, B N, x *.
Пусть грамматика G = (N, , P, S) задается следующим образом:
N = {S, L}, = {a, b, 0, 1},
P = {S→aL, S→bL, S→a, S→b,
L→aL, L→bL, L→0L, L→1L,
L→a, L→b, L→0, L→1}.
Данная грамматика является регулярной с правосторонними продукциями и порождает такие цепочки, которые начинаются только с буквы.