Эквивалентность языков мп-автоматов и кс-грамматик

Пусть задана КС-грамматика G(VT,VN,P,S). Построим на ее основе МП-автомат R({q},VT,VTuVN,λ,q,S,{q}). Этот автомат имеет только одно состояние. Определим функцию переходов автомата следующим образом:

Начальная конфигурация автомата: (q,a,S); конечная конфигурация автомата: (q,λ,λ).

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

--- если в грамматике G существует вывод А=>*a, то автомат R может сделать последовательность шагов (q,a,A)/*(q,λ,λ), где AeVN — некоторый произвольный нетерминальный символ грамматики, а aeVT*;

--- если автомат R может сделать последовательность шагов (q,a,A)/*(q,λ,λ), то в грамматике G существует вывод А=>*а.

Докажем первое утверждение. Доказательство будем вести на основе математической индукции. Положим, что в грамматике G существует вывод A=>^ma для некоторого m > 0.

Для m = 1 имеем А=>а, а = а1..а2 k>0. Тогда если k = 0, то a =λ, и должно существовать правило грамматики А-»λ, а по определению автомата R имеем:

(q,a,A) •*• (q,λ,λ,). Если k > 0, то должно существовать правило грамматики А-»а, и по определению автомата R получаем:

(q,aia₂...a_k,A) / (q,a₁a₂...a_k,a₁a₂...a_k) / (q,a₂...a_k,a₂...a_k) / ... / (q,a_k,a_k) / (q,λ,λ), следовательно,

(q,a₁a₂...a_k,A) * (q,a,a₂...a_k,a₁a₂...a_k) /^k (q,λ,λ) и (q,aia₂,..a_k,A) /* (q,λ,λ).

Таким образом, утверждение для m = 1 доказано.

Предположим, что для некоторого т>1 это утверждение справедливо. Значит, если существует вывод А=>^та в грамматике G, то существует и последовательность шагов автомата R: (q,a,A) /* (q,λ,λ,).

Следуя принципу математической индукции, докажем теперь, что это утверждение справедливо и для некоторого m+1. То есть докажем, что если существует вывод A=>^m+1a в грамматике G, то существует и последовательность шагов автомата R: (q,a,A)-b*(q,λ,λ,).

Рассмотрим первый шаг вывода A=>^m+1a: A=>X1X₂...X_k, где V k>i>0: Xie(VTuVN). Если X1eVN, то существует вывод X1 =>^mi x_i причем XjeVT* и m<m; если же X1eVT, то X=Xi. Саму исходную цепочку а можно записать как конкатенацию цепочек терминальных символов х_i: a = X1X₂...X_k.

Если первый шаг вывода A=>X1X₂...X_k, тогда в грамматике G существует правило A—»X1X₂...X_k, и, по определению автомата R, первым шагом его работы может быть шаг: (q,a,A) / (q,a,X₁X₂...X_k).

Но для всех XjeVN, так как V k > i > 0: X1 =>^mi Xj и nij < m, то по утверждению индукции имеем (q,Xj,Xj) ч-* (q,λ,λ).

А для всех XjeVT по определению автомата R имеем (q.xi,Xj)/(q,X,X).

Объединяя шаги работы автомата R для всех Xj из конфигурации (q,a,X,X₂...X_k), получаем (q,a,XtX₂...X_k) -=-* (q,A.,A,), следовательно, (q,a,A) / (q,a,XiX₂...X_k) =* (q,λ,λ), и отсюда можно утверждать, что (q,a,A) /* (q,λ,λ).

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

Докажем второе утверждение. Доказательство будем вести на основе математической индукции. Положим, что автомат R может выполнить последовательность шагов (q,a,A) /^п (q,λ,λ) для некоторого n > 0.

Если п = 1, тогда имеем один шаг работы автомата: (q,a,λ)/(q,λ,λ,) и, следовательно, a = λ. Отсюда, согласно определению автомата R, в грамматике G должно существовать правило вида А-»λ. Тогда в грамматике G существует и вывод А=>А, или, что то же самое, А=>*а. Для п = 1 утверждение доказано.

Предположим, что для некоторого п>1 это утверждение справедливо. Значит, если существует последовательность шагов работы автомата R: (q,a,A) =* (q,λ,λ), то в грамматике G существует вывод А=>*а.

Теперь докажем, что это утверждение справедливо и для некоторого n+1. Рассмотрим последовательность шагов работы автомата R: (q,a,A) /ⁿ⁺¹ (q,λ,λ). Первым шагом этой последовательности будет шаг (q,a,A) / (q,a,XiX₂...X_k), V k > i > 0: Xje(VTuVN). Причем, по определению автомата R, в грамматике G должно существовать правило вида A->X₁X₂...X_k. Можно утверждать, что V XjE(VTuVN), (q,Xj,Xj) *ⁿi (q,λ,λ), х_;еУТ*, причем а = X1X₂...x_k, и в грамматике G существует вывод Хi>*хi.

Действительно, если ХiеVN и (q,Xi,Xi) +ⁿi (q,λ,λ), XieVT, то по сделанному предположению индукции справедливо утверждение, что существует вывод Xi=>*Xi в грамматике G, так как Vi: ni<n.

Если же XieVT, то по определению автомата R: (q,Xi,Xi)=(q,λ,λ), Xi=Xi, что соответствует выводу X_i=>°x_i, и тогда также справедливо Хi=>*Хi.

Тогда можно построить левосторонний вывод в грамматике G: A => X!X₂...X_k =>* x₁X₂...X_k =>* X1X₂...X_k =>* ... =>* X1X₂...x_k = а. Следовательно, в грамматике G существует вывод А =>* а.

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

Поскольку из двух доказанных утверждений однозначно следует, что в КС-грамматике G существует вывод S =>* а (где S — целевой символ грамматики) тогда и только тогда, когда в МП-автомате R существует последовательность шагов работы автомата (q,a,S) /* (q,λ,λ), то можно утверждать, что построенный МП-автомат R распознает язык, заданный КС-грамматикой G: L(R) = L(G). Поскольку построенный МП-автомат допускает входные цепочки языка с опустошением стека, то доказано также утверждение L_X(R) = L(G).

При доказательстве на структуру правил грамматики G не накладывалось никаких дополнительных ограничений, поэтому все доказанные утверждения справедливы для произвольной КС-грамматики.

После того как доказано, что для произвольной КС-грамматики всегда можно построить МП-автомат, распознающий заданный этой грамматикой язык, можно говорить, что МП-автоматы распознают КС-языки. На самом деле существует также и доказательство того, что для произвольного МП-автомата всегда можно построить КС-грамматику, которая задает язык, распознаваемый этим автоматом. Таким образом, КС-грамматики и МП-автоматы задают один и тот же тип языков — КС-языки.

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

Здесь используется представление о том, что обозначение «=>*» включает в себя также понятие «вывод с нулевым количеством шагов», которое обозначается «=>°» и на самом деле означает, что две цепочки символов совпадают (равны). Если каждая цепочка состоит из одного символа, то символы двух цепочек эквивалентны между собой. Эта особенность упоминалась, когда вводилось понятие — «а =>* β» — «цепочка β выводима из цепочки а», но до настоящего момента явно нигде не использовалась. В данном случае это не влияет на структуру доказательства, но очень удобно, поскольку не требует ввода дополнительного обозначения для понятия «цепочка р выводима из цепочки а или совпадает с нею».