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}.

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