Теория языков программирования методов трансляции (стр. 9 )

Рис. 3.1. Распознаватель

Функция доступа к памяти – это отображение множества возможных состояний или конфигураций памяти в конечное множество информационных символов.

Функция преобразования памяти – это отображения, описывающие её изменения. Вообще, именно тип памяти определяет название распознавателя (распознаватель магазинного типа).

Управляющее устройство – это программа, управляющая поведением распознавателя. Управляющее устройство представляет собой конечное множество состояний вместе с отображением, которое описывает, как меняются состояния в соответствии с текущим входным символом (т. е. находящимся под входной головкой) и текущей информацией, извлечённой из памяти. Управляющее устройство определяет также, в каком направлении сдвинуть головку и какую информацию поместить в память.

Распознаватель работает, проделывая некоторую последовательность шагов или тактов.

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

1)  входная головка сдвигается на одну ячейку влево, вправо или остаётся в исходном положении;

2)  в памяти помещается некоторая информация;

3)  изменяется состояние управляющего устройства.

Поведение распознавателя обычно описывается в терминах конфигураций распознавателя. Конфигурация – это «мгновенный снимок» распознавателя, на котором изображены:

1)  состояние управляющего устройства;

2)  содержимое входной ленты вместе с положением головки;

3)  содержимое памяти.

Управляющее устройство может быть детерминированным либо недетерминированным.

В детерминированном устройстве для каждой конфигурации существует не более одного возможного следующего шага.

Недетерминированное устройство – это просто удобная математическая абстракция, не реализуемая на практике.

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

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

Распознаватель допускает входную цепочку w, если, начиная с начальной конфигурации, в которой цепочка w записана на входной ленте, распознаватель может проделать конечную последовательность шагов, заканчивающуюся конечной конфигурацией.

Язык, определяемый распознавателем – это множество входных цепочек, которые он допускает.

Для каждого класса грамматик из иерархии Хомского существует естественный класс распознавателей:

1)  язык L праволинейный тогда и только тогда, когда он определяется односторонним детерминирванным конечным автоматом;

2)  язык L – контекстно-свободный тогда и только тогда, когда он определяется односторонним недетерминированным автома-том с магазинной памятью;

3)  язык L контекстно-зависимый тогда и только тогда, когда он определяется двусторонним недетерминированным линейно-ограниченным автоматом;

4)  язык L рекурсивно перечисляемый тогда и только тогда, когда он определяется машиной Тьюринга.

3.5.  Регулярные множества, их распознавание и порождение

Рассмотрим методы задания языков программирования и класс множеств, образующий этот класс языков. Основным аппаратом задания будут регулярные множества и регулярные выражения на них.

Определение.

Пусть S - конечный алфавит. Регулярное множество в алфавите S определяется рекурсивно следующим образом:

1)  Æ – (пустое множество) – регулярное множество в алфавите S;

2)  {e} – регулярное множество в алфавите S;

3)  {a} – регулярное множество в алфавите S для каждого аÎS;

4)  если Р и Q – регулярное множество в алфавите S, то таковы же и множества:

а) PÈQ;

б) PQ;

в) P*;

5)  ничто другое не является регулярным множеством в алфавите S.

Таким образом, множество в алфавите S регулярно тогда и только тогда, когда оно либо Æ, либо {e}, либо {а} для некоторого аÎS, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

Определение.

Регулярные выражения в алфавите S и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом:

1)  Æ – регулярное выражение, обозначающее регулярное множество Æ;

2)  е – регулярное выражение, обозначающее регулярное множество {e};

3)  если аÎS, то а – регулярное выражение, обозначающее регулярное множество {a};

4)  если р и q – регулярные выражения, обозначающие регулярные множества Р и Q, то

а) (p+q) – регулярное выражение, обозначающее РÈQ;

б) pq – регулярное выражение, обозначающее PQ;

в) (р)* - регулярное выражение, обозначающее Р*;

5)  ничто другое не является регулярным выражением.

Принято обозначать р+ для сокращенного обозначение рр*. Расстановка приоритетов:

-  * (итерация)- наивысший приоритет;

-  конкатенация;

-  +.

Таким образом, 0 + 10* = (0 + (1 (0*)))

Пример.

01 означает {01}

0* {0*}

(0+1)* {0, 1}*

(0+1)* 011 – означает множество всех цепочек, составленных из 0 и 1 и оканчивающихся цепочкой 011.

(а+b) (а+b+0+1)* означает множество всех цепочек {0,1,a,b}*, начинающихся с а или b.

(00+11)* ((01+10)(00+11)* (01+10)(00+11)*) обозначает множество всех цепочек нулей и единиц, содержащих четное число 0 и чётное число 1. Таким образом для каждого регулярного множества можно найти регулярное выражение, его обозначающее, и наоборот.

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

Пусть a, b и g регулярные выражения, тогда:

1)  a + b = b + a

2)  Æ* = е

3)  a + (b + g) = (a+b)+g

4)  a(bg)=(ab)g

5)  a(b+g)=ab+ag

6)  (a+b)g=ag+bg

7)  aе = еa = a

8)  Æa=aÆ=Æ

9)  a*=a+a*

10)  (a*)*=a*

11)  a+a=a

12)  a+Æ=a.

При работе с языками часто удобно пользоваться уравнениями, коэффициентами и неизвестными которых служат множества. Такие уравнения будем называть уравнениями с регулярными коэффициентами

,

где а и b– регулярные выражения. Можно проверить прямой подстановкой, что решением этого уравнения будет а*b.

,

т. е. получаем одно и то же множество. Таким же образом можно установить и систему уравнений.

Определение. Систему уравнений с регулярными коэффициентами назовём стандартной системой с множеством неизвестных , если она имеет вид:

где – регулярные выражения в алфавите, не пересекающемся с D. Коэффициентами уравнения являются выражения .

Если =Æ, то в уравнении нет числа, содержащего . Аналогично, если =е, то в уравнении для член, содержащий - это просто . Иными словами, Æ играет роль коэффициента 0, а е – роль коэффициента 1 в обычных линейных уравнениях.

Алгоритм решения стандартной системы уравнений с регулярными выражениями.

Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите S и множеством неизвестных .

Выход. Решение системы Q.

Метод: Аналог метода решения системы линейных уравнений методом исключения Гаусса.

Шаг 1. Положить i = 1.

Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для в виде , где a - регулярное выражение в алфавите S, а b - регулярное выражение вида: , причём все – регулярные выражения в алфавите S. Затем в правых частях для уравнений заменим регулярным выражением .

Шаг 3. Увеличить i на 1 и вернуться к шагу 2.

Шаг 4. Записать уравнение для в виде , где a и b - регулярные выражения в алфавите S. Перейти к шагу 5 (при этом i=n).