Определение m: n - ограниченного контекста

Так же, как и в простом предшествовании, расширим ограниченный контекст до m:n символов.

Пусть имеем правило U:=u ,где для каждой пары цепочек:

|V| = m;

|W| = n.

И некоторый вывод: Z => +..VuW...

Цепочка u является основой сентенциальной формы, и данная цепочка u может быть заменена на нетерминал U. Такое правило m:n - ограниченно контекстное, в то время как R[W](то есть R содержит W)содержит R входных символов. В этом случае можно заменить u на U.

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

3.4. Автоматы с магазинной памятью, [ мп-автомат ]

Конечные автоматы успешно решали задачи распознавания цепочек, построенных на основе автоматической грамматики. Но эта грамматика не в состоянии охватить всё множество конструкций языков программирования. Более приемлемой является КС-грамматика. Для распознавания цепочек генерируемых КС-грамматикой вводят понятие МП-автомат. Как и в случае с КА, обработка осуществляется за несколько шагов. В отличие от КА, МП может обработать входной символ в течение нескольких шагов. Каждый шаг процесса определяется несколькими правилами, то есть состоянием автомата, верхним символом магазина и текущим символом входной цепочки.

Операции над магазином:

1. выбрать символ из магазина;

2. заслать в магазин;

3. оставить в магазине без изменения.

Операции над состоянием:

1. оставить в прежнем состоянии;

2. перейти в новое состояние.

Операции над входной цепочкой:

1. перейти к следующему входному символу;

1. остаться на прежнем символе.

Обработку входной цепочки МП-автомат начинает в некотором выделенном состоянии при определённом содержимом магазина. Сканируемый символ является первым символом входной цепочки, затем автомат выполняет операции, задаваемые ему управляющим устройством. Автомат не должен требовать следующий входной символ, если текущий символ стека - концевой маркер (магазин пуст).

Автомат задаётся:

2. конечным множеством входных символов;

3. конечным множеством магазинных символов, включая маркер;

4. некоторой функцией, обеспечивающей переход из одного состояния в другое.

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

МП={Q, , Г, , q₀, Г₀, F};

Q - множество состояний;

S - входной алфавит;

Г - алфавит магазинных символов;

- функция отображения, обеспечивающая преобразование: ;

q₀- начальное состояние;

Г₀- начальный символ магазина;

F - множество заключительных символов: .

Конфигурация автомата определяется символами (q, W, S), где (цепочка входных символов).

Переход из одного состояния в другое - бинарная операция:

(q₀, W, Z)|- (q₁, W, Z).

Это имеет место тогда и только тогда, когда .

Цепочка принимается автоматом, если возможен переход: |― ,

где - начальное состояние, е - пустая цепочка ( ).

Любая программа может быть записана в постфиксной форме.

Функция отображения: , где - символ, - подмножество символов.

Автоматы могут не считывать ничего из входной цепочки, а работать только с магазином. Если магазин пуст, то автомат считывает символ из входной цепочки.

Язык: . Верхний символ магазина - левый символ цепочки - загружаем в магазин и сравниваем. Если цепочка считана и в магазине - маркер дна, то цепочка принята автоматом.

1. 

0

0

0

1

1

1

- загрузка, - сравнение, - заключительное состояние (цепочка принята или нет).

, - не знаем;

- начальное состояние;

Z- начальные символы магазина; МП= ;

- заключительное состояние.

Функция отображения:

Автомат детерминированный.

1. - 0 в магазин;

2. - загрузка магазина;

3. - сравнение 1 и 0;

4. - убираем маркер.

Рассмотрим 0011:

|- |- |- |- |- .

Рассмотрим :

|- за n шагов |- |- |- за (n-1) шаг |- |- .

Автомат может продолжить работу далее, если он прочёл всю входную цепочку, но не сделает следующего шага, так как магазин пуст.

2. ;

(обращение);

;

;

1. ;

2. ;

3. - появилась недетерминированность;

4. .

Однозначно можно сравнить и загрузить в автомат:

;

;

;

.

Рассмотрим aabbbbaa:

|-  |- |- ;

|- ^(*)(*)|-  |-  ^(**)|- ;

|- |-  |-  |-  .

Если автомат недетерминированный, его распознавательная способность гораздо мощнее.

Рис.1. Блок-схема алгоритма

Пример: .

- загрузка (начальное состояние), - сравнение, - заключительное

состояние (принята или нет цепочка).

,

Z- начальные символы магазина;

МП= ;

Функция отображения:

1. - 0 в магазин;

2. - загрузка магазина;

3. - сравнение 1 и 0 при q₀;

4. - сравнение 1 и 0 при q₁;

5. - убираем маркер.

1. Рассмотрим допустимую цепочку 0011.

Загрузка начального (выделенного) состояния

Итерация 1:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |― .

Магазин пуст? Нет.

Итерация 2:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 3:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 1.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 4:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 1.

Выполнение операций, задаваемых управляемым устройством |― .

Магазин пуст? Да.

Входная цепочка пуста? Да.

Цепочка символов входного алфавита является допустимой.

2. Рассмотрим недопустимую цепочку 001.

Загрузка начального (выделенного) состояния .

Итерация 1:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |― .

Магазин пуст? Нет.

Итерация 2:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 3:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 1.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 4:

Входная цепочка пуста? Да.

Цепочка символов входного алфавита является недопустимой.