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

1) Понятие и формальное определение грамматики. Грамматика как способ задания языка. Описание языка программирования посредством грамматик. Проиллюстрировать на примере (пример должен быть свой).
2) Автоматы с магазинной памятью (МПА) как распознаватели КС-языков; необходимые определения (такт, конфигурация, функция перехода), классификация МПА. Проиллюстрировать на примерах (примеры должны быть свои).
3) Построить СУ-схему обращения цепочек, т.е. перевода (w, wR), где w  {a,b,c}*. Построить преобразователь с магазинной памятью с опустошением стека для выполнения этого же перевода. ...

-

Определения (такт, конфигурация, функция перехода)
Общая условная схема автомата с магазинной памятью (МП-автомата)
Конфигурация МП-автомата описывается в виде тройки (q,,)QxV*xZ* , кото­рая определяет текущее состояние автомата q, цепочку еще непрочитанных сим­волов  на входе автомата и содержимое магазина (стека). Вместо а в конфи­гурации можно указать пару (,n), где V*— вся цепочка входных символов, а nN{0}, n 0 — положение считывающего указателя в цепочке.
При выполнении такта (перехода) из стека удаляется верхний символ, соответствующий условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и тем самым он будет входным символом при следующемпереходе). Эти переходы (такты) называются -переходами. Аналогично, автомат не обязательно должен извлекать символ из стека — когда z=., этого не происходит.
Автомат имеет конечное множе­ство состояний, конечное множество входных символов и неограниченную снизу вспомогательную ленту (называемую лентой магазинной памяти или магазинной памятью). «Дно» магазина (самый нижний символ) отмечается специальным символом, называемым маркером дна. Пусть это будет символ #. Магазинная память определяется свойством «первым введен — последним выведен». При записи символа в магазин, его содержимое сдвигается на одну ячейку «вниз», а на освободившееся место записывается требуемый символ. В этом случае говорят, что символ «вталкивается» в магазин.
Для чтения доступен только самый последний (т.е. верхний) символ магазина. Этот символ после чтения может либо остаться в магазине, либо быть удален из него, т.е. «вытолкнут» из магазина. За один такт работы МП-автомата из .магазина можно удалять не более одного символа.
Каждый шаг работы МП-автомата задается множеством правил перехода ав­томата из одних состояний в другие. Переходы в общем случае определяются:
состоянием МП-автомата;
верхним символом магазина;
текущим входным символом.
Классификация МПА
Детерминированные и недетерминированные МА.
Различают детерминированные и недетерминированные МА. Если среди команд МА нет двух таких, у которых совпадают части, стоящие слева от стрелки, и не совпадают части, стоящие справа от стрелки, то МА называют детерминированным. В противном случае, т.е. когда для заданно­го состояния и текущих входном и магазинном символах возможны переходы автомата в различные состояния, его называют недетерминированным.
Для недетерминированных автоматов (в отличие от детерминированных) существует два эквивалентных критерия завершения работы:
пустой магазин;
достижение конечного состояния.
Детерминированный автомат завершает работу лишь тогда, когда достигает конечного состояния.
Рассмотрим более формальные определения.
M=(Q,V,Г ,,qo,zo,F) является детерминированным, если:
1) для любых qQ, ZГ и а(V{}) значение #(q,a,Z)≤1;
2) для любых qQ, ZГ, всякий раз, как (q,,Z)≠, значение (q,a,Z)= , для любого а  V.
Стоит отметить, что класс языков, принимаемых недетерминированными МА, есть в точности класс КСЯ.
Теорема. Если L – КС язык, то существует недетерминированный магазинный автомат М, такой что L=N(M)
МА, распознающие по конечному состоянию (F-автоматы), и по опустошению магазина (N-автоматы).
МА допускает цепочку символов w, если, получив эту цепочку на вход, он может перейти в одну из конечных конфигураций, когда по окончании цепочки автомат находится в одном из конечных состояний: (q0,w,z0)├─*(q,,z), где qF, zZ*. После окончания прочтения цепочки автомат может проделать некоторое количество –тактов.
Язык, определяемый МП-автоматом P – это множество всех цепочек символов, допускаемых этим автоматом:
L(P) = {w | qF | (q0,w,z0)├─*(q,,z), где zZ* }.
Два автомата P1 и P2 эквивалентны, если они определяют один и тот же язык: L(P1)=L(P2).
Говорят, что МПА допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из своих конечных состояний, а стек пуст, т.е. получена конфигурация (q,,), qF.
То есть, условием остановки МПА может быть два случая:
1) Автомат находится в одном из конечных состояний (F-автомат).
2) Магазин (стек) пуст (N-автомат).
Проиллюстрировать на примерах (примеры должны быть свои)
Приведем примеры.
Пример 1.
МПА, распознающий цепочки языка anbn
 (q , a , Z0) = (q , Z0a),
 (q1 , a , a) = (q1 , aa),
 (q1 , b , a) = (q2 , ),
 (q2 , b , a) = (q2 , ),
 (q2 ,  , Z0) = (q, ).
Продемонстрируем работу на цепочке языка
(q,aabb,Z0) ├ (q1,abb,Z0a) ├ (q1,bb,Z0aa) ├ (q2,b,Z0a) ├ (q2,,Z0) ├ (q,,) .
Пример 2.
Автомат, распознающий язык, цепочками которого являются арифметические выражения.
P = {a, +, *, ), ( }, Z = {E, T, F, a, +, *) , h0, ( }, S = {s0 }, F = {s0}
(s0 ,  , E) = {(s0 , T+E) ; (s0 , T)},
(s0 ,  , T) = {(s0 , F*T) ; (s0 , F)},
 (s0 ,  , F) = {(s0 , (E) ) ; (s0 , a)},
 ( s0, a, a ) = ( s0, ),
 ( s0 , + , + ) = (s0 ,  ),
 ( s0 , * , * ) = (s0 ,  ),
 ( s0 , ( , ( ) = (s0 ,  ),
 ( s0 , ) , ) ) = (s0 ,  ),
 (s0 ,  , h0) = ( s0 ,  ).
Продемонстрируем работу автомата:
(s0 , a+a*a , h0E) ├ (s0 , a+a*a , h0T+E) ├ (s0 , a+a*a , h0T+T) ├ (s0 , a+a*a , h0T+F) ├ (s0 , a+a*a , h0T+a) ├ (s0 , +a*a , h0T+) ├ (s0 , a*a , h0T) ├ (s0 , a*a , h0F*T) ├ (s0 , a*a , h0F*F) ├ (s0 , a*a , h0F*a) ├ (s0 , *a , h0F* ) ├ (s0 , a , h0F) ├
(s0 , a , h0a) ├ (s0 ,  , h0) ├ (s0 ,  , ).
Пример 3.
Магазинный автомат для языка L={wwR| w{a,b}*}
D:
(q0,a, ) ={(q0, Z1)}