Лекция 14 Магазинные автоматы Детерминированные магазинные автоматы и детерминированные кс-языки

Е сли НМА таков, что каждый его шаг определен однозначно (т.е. отсутствует выбор при переходе из одной конфигурации в другую), то такой автомат называется детерминированным магазинным автоматом-распознавателем (ДМА). Дадим определение ДМА, основываясь на определении 12.1.

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

Магазинный автомат

M = (Q, , V, , q₀, z₀, F)

называется детерминированным, если он является НМА в соответствии с определением 12.1 и удовлетворяет следующим ограничениям: для любых q  Q, a    {} и b  V

1. |(q, a, b)|  1, т.е. (q, a, b) содержит не более одного элемента,

2. если (q, , b) ¹ , то для любого а   (q, a, b) = .

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

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

Язык L называется детерминированным контекстно‑свобод-ным языком (ДКС-языком), если существует ДМА М такой, что L = L(M).

Пример 14.3.

Покажем, что язык

L = {aⁿbⁿ | n  0}

является детерминированным контекстно-свободным языком.

Нетрудно убедится, что

М = ({q₀, q₁, q₂}, {a, b}, {0, 1}, , q₀ , 0, {q₀}),

где  определена соотношениями

(q₀, a, 0) = {(q₁, 10)},

(q₁, a, 1) = {(q₁, 11)},

(q₁, b, 1) = {(q₂, )},

(q₂, b, 1) = {(q₂, )},

(q₂, , 0) = {(q₀, )},

является ДМА и допускает язык L.

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

Пример 14.4.

Возьмем два языка:

L₁ = {aⁿbⁿ | n  0}

и

L₂ = {aⁿb²ⁿ | n  0}.

Как ранее было показано, язык L₁ контекстно-свободный. Несложной модификацией грамматики языка L₁ можно получить КС-грамматику для L₂, значит, L₂ – тоже КС-язык.

Покажем, что язык

L = L₁  L₂

является контекстно-свободным. Это можно сделать разными способами. Пусть, скажем,

G₁ = (N₁, T, S₁, P₁)

и

G₂ = (N₂, T, S₂, P₂)

– КС-грамматики, порождающие языки L₁ и L₂, соответственно. Предположим, что N₁  N₂ =  и S  N₁  N₂. Построим грамматику G, являющуюся комбинацией грамматик G₁ и G₂:

G = (N₁  N₂  {s}, T, S, P),

где

P = P₁  P₂  {s  s₁, s  s₂}.

Нетрудно показать, что G порождает язык L, а следовательно, L – контекстно-свободный язык. Покажем, что L не является детерминированным КС-языком. Рассуждение построим следующим образом: предположив, что L – детерминированный КС-язык, приходим к заключению, что язык

L' = L  {aⁿbⁿcⁿ | n  0}

должен тогда быть контекстно-свободным, а это не так.

Для доказательства того, что L' будет КС-языком, если L – детерминированный КС-язык, построим НМА M', распознающий L', основываясь на ДМА М, распознающем L.

Идея построения этого НМА заключается в том, чтобы добавить к устройству управления автомата М аналогичный блок, в котором переходы, осуществляемые при чтении входного символа b, заменены на аналогичные переходы для символа с. Этот новый блок устройства управления вступает в работу после того, как М заканчивает чтение aⁿbⁿ. Так как этот второй блок реагирует на сⁿ совершенно так же, как первый (основной) блок на bⁿ, то процесс распознавания aⁿb²ⁿ превращается теперь в процесс распознавания строки aⁿbⁿcⁿ. На рис. 14.1 эта конструкция изображена схематически.

bⁿ аⁿbⁿ Диаграмма М

 

Диаграмма

сⁿ дополнительного

блока

Рис. 14.1. Диаграмма переходов M'

Итак, пусть

M = (Q, , V, , q₀, z₀, F),

где

Q = {q₀, q₁, ..., q_n}.

Рассмотрим

M' = (Q', , V,   ', q₀, z₀, F' ),

где

Q' = Q  {q'₀, q'₁, ..., q'_n},

F' = F  {q'_i | q_i  F},

а функция ' построена из  добавлением соотношений

'(q_f, , x) = {(q'_f, x)}

для всех q_f F и х  V

и

'(q'_i, c, x) = {(q'_j, )}

для всех (q_i, b, x) = {(q_j, )} и

q_i  Q, x  V,   V*.

Для М распознать строку aⁿbⁿ означает выполнение соотношения

(q₀, aⁿbⁿ, z₀) (q_i, , ), где q_i  F.

Так как М – детерминированный, должно также выполняться соотношение

(q₀, aⁿb²ⁿ, z₀) (q_i, bⁿ, ),

откуда следует, что для распознавания строки aⁿb²ⁿ необходимо выполнение соотношения

(q_i, bⁿ, ) (q_j, , ),

где q_i – некоторое заключительное состояние из F. Но тогда, по построению автомата М', мы имеем:

(q'_i, cⁿ, ) (q'_j, , ),

т.е. M' допускает строку aⁿbⁿcⁿ. Нетрудно видеть, что никаких других строк, кроме тех, которые содержатся в L', НМА M' не допускает. Следовательно, L' = L(M'), а это значит, что L' – контекстно-свободный язык. Но это не так!

В следующей лекции, применяя Лемму о расширении, мы покажем (пример 15.8), что L' не является КС-языком. Поэтому наше исходное предположение о том, что L – детерминированный КС-язык, неверно.

Тем самым мы показали, что класс детерминированных КС-языков является собственным подмножеством класса всех КС-языков.