Основные определения. Будем представлять магазин (магазинный список, магазинную ленту) как и входную ленту в виде цепочки символов

Будем представлять магазин (магазинный список, магазинную ленту) как и входную ленту в виде цепочки символов, причем верхним элементом магазина будем считать самый левый или самый правый символ цепочки в зависимости от того, что удобнее в данной ситуации. Пока будем считать верхним самый левый символ.

Автомат с магазинной памятью (сокращенно МП-автомат) - это семерка

R = (Q, S, G, d, q₀, Z₀, F)

где

(1) Q - конечное множество символов состояний управляющего устройства;

(2) S - конечный входной алфавит;

(3) G - конечный алфавит магазинных символов;

(4) d - отображение множества Q ´(SÈ{e})´G в множество конечных подмножеств множества Q ´G ^*;

(5) q₀Î Q - начальное состояние управляющего устройства;

(6) Z₀ Î G - символ, находящийся в магазине в начальный момент (начальный символ магазина);

(7) F Í Q - множество заключительных состояний.

Конфигурацией МП-автомата называется тройка

(q, a, b) Î Q´S ^* ´G ^*,

где

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

(2) a - неиспользованная часть входной цепочки; первый символ цепочки a находится под входной головкой; если a = e, то считается, что входная лента прочитана;

(3) b - содержимое магазина; левый символ цепочки b считается верхним символом магазина; если b = e, то магазин считается пустым.

Такт работы автомата будем представлять в виде бинарного отношения перехода ú¾, определенного на конфигурациях. Будем писать

(q, aa, cb) ú¾ (q^½, a, gb),

если множество d (q, a, c) содержит (q ^½, g), где q, q ^½Î Q, a Î SÈ{e}, aÎ S ^*, c Î G и b, gÎ G ^*.

Если a¹e, то говорят, что МП-автомат R, находясь в состоянии q и имея a в качестве текущего входного символа, расположенного под входной головкой, а c в качестве верхнего символа магазина, может перейти в новое состояние q^½, сдвинуть входную головку на ячейку вправо и заменить верхний символ магазина цепочкой g магазинных символов. Эта цепочка может совпадать с заменяемым символом c. Если g =e, то верхний символ удаляется из магазина, и тем самым магазинный список сокращается.

Если a=e, будем называть этот такт e -тактом. В e -такте текущий входной символ не принимается во внимание и входная головка не сдвигается. Однако состояние управляющего устройства и содержимое магазина могут измениться. Заметим, что e -такт может происходить и тогда, когда вся входная цепочка прочитана.

Следующий такт невозможен, если магазин пуст.

Отношение ú¾ ⁱ традиционно обозначает выполнение i тактов (i ³ 0); ú¾^* - реф­лек­­сив­но-транзитивное (i ³ 0), а ú¾ ⁺ - транзитивное (i > 0) замыкание отношения ú¾.

Начальной конфигурацией МП-автомата R называется конфигурация вида

(q₀, a, Z₀),

где aÎ S ^*, т.е. управляющее устройство находится в начальном состоянии q₀, входная лента содержит цепочку a, которую нужно распознать, а в магазине есть только начальный символ Z₀.

Заключительная конфигурация - это конфигурация вида

(q, e, b),

где q Î F и bÎ G ^*.

Говорят, что цепочка a допускается МП-автоматом, если

(q₀, a, Z₀) ú¾ ^* (q, e, b)

для некоторых q Î F и bÎ G ^*.

Языком, определяемым (или допускаемым) МП-автоматом R (обозначается L(R)), называется множество цепочек, допускаемых автоматом R.

Пример 6.1. Построим МП-автомат, определяющий язык

L = { 0 ⁿ 1 ⁿ ½ n ³ 0 }.

Пусть

R = ({q₀, q₁, q₂}, {0, 1}, {z, 0}, d, q₀, z, {q₀}),

где

d (q₀ , 0, z) = {(q₁ , 0z)}

d (q₁ , 0, 0) = {(q₁ , 00)}

d (q₁ , 1, 0) = {(q₂ , e)}

d (q₂ , 1, 0) = {(q₂ , e)}

d (q₂ , e, z) = {(q₀ , e)}

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

(q₀ , 0011, z) ú¾ (q₁ , 011, 0z)

ú¾ (q₁ , 11, 00z)

ú¾ (q₂ , 1, 0z)

ú¾ (q₂ , e, z)

ú¾ (q₀ , e, e)

Вообще можно показать, что

(q₀ , 0, z) ú¾ (q₁ , e, 0z)

(q₁ , 0 ⁱ, 0z) ú¾ ⁱ (q₁ , e, 0 ⁱ⁺¹z)

(q₁ , 1, 0 ⁱ⁺¹z) ú¾ (q₂ , e, 0 ⁱz)

(q₂ , 1 ⁱ, 0 ⁱz) ú¾ ⁱ (q₂ , e, z)

(q₂ , e, z) ú¾ (q₀ , e, e)

Объединяя все это, получаем для n ³ 1

(q₀ , 0 ⁿ1 ⁿ, z) ú¾ ²ⁿ⁺¹ (q₀ , e, e)

и

(q₀ , e, z) ú¾ ⁰ (q₀ , e, e)

Таким образом, L Í L(R).

Покажем, что L Ê L(R), т.е. что R допускает только цепочки вида 0 ⁿ1ⁿ. Эта часть доказательства труднее. Обычно легче доказать, что такие-то цепочки распознаватель допускает, и так же, как для грамматик, гораздо труднее доказать, что он допускает цепочки только определенного вида.

В данном случае заметим, что если R допускает непустую цепочку, то он должен пройти через состояния q₀ , q₁ , q₂ , q₀ именно в этом порядке.

Далее, если (q₀ , j, z) ú¾ ⁱ (q₁ , e, y), то j = 0 ⁱ и y = 0 ⁱz. Аналогично, если (q₂ , j, y) ú¾ ⁱ (q₂ , e, l), то j = 1 ⁱ и y = 0 ⁱl. К тому же (q₁ , j, y) ú¾ (q₂ , e, l) только тогда, когда j = 1 и y = 0l, а (q₂ , j, z) ú¾ ^* (q₀ , e, e) только тогда, когда j = e. Таким образом, если (q₀ , a, z) ú¾ ⁱ (q₀ , e, b) для некоторого i ³ 0, то либо a = e и i = 0, либо a = 0 ⁿ1ⁿ, i = 2n+1 и b = e. Следовательно, L Ê L(R). 

Пример 6.2. Построим МП-автомат, допускающий язык

L = {aa ^R ½ a Î {a, b} ⁺}

Пусть

R = ({q₀ , q₁ , q₂ }, {a, b}, {Z, a, b}, d, q₀ , Z, {q₂ }),

где

(1) d (q₀ , a, Z) = {(q₀ , aZ)}

(2) d (q₀ , b, Z) = {(q₀ , bZ)}

(3) d (q₀ , a, a) ={(q₀ , aa), (q₁ , e)}

(4) d (q₀ , a, b) = {(q₀ , ab)}

(5) d (q₀ , b, a) = {(q₀ , ba)}

(6) d (q₀ , b, b) ={(q₀ , bb), (q₁ , e)}

(7) d (q₁ , a, a) ={(q₁ , e)}

(8) d (q₁ , b, b) ={(q₁ , e)}

(9) d (q₁ , e, Z) = {(q₂ , e)}

МП-автомат R вначале копирует в магазине какую-то часть входной цепочки по правилам (1), (2), (4) и (5) и первым альтернативам правил (3) и (6). Однако R - недетерминированный распознаватель. В любой момент, когда текущий входной символ совпадает с верхним символом магазина, он может перейти в состояние q₁ и начать сравнивать цепочку в магазине с оставшейся частью входной цепочки. Этот выбор осуществляют вторые альтернативы правил (3) и (6), а по правилам (7) и (8) происходит сравнение. Если R обнаруживает несовпадение очередных символов, то этот экземпляр МП-автомата “умирает”, т.е. перестает работать. Однако, так как автомат R - недетерминированный, то разные его экземпляры могут дать все возможные для него такты. Если какой-то выбор тактов приводит к тому, что Z снова оказывается верхним (и единственным) символом магазина, то по правилу (9) R стирает Z и попадает в заключительное состояние q₂ . Итак, R допускает цепочку тогда и только тогда, когда все сравнения обнаружили совпадение символов.

Например, для входной цепочки abba автомат R может среди прочих сделать следующие последовательности тактов:

(1) (q₀ , abba, Z) ú¾ (q₀ , bba, aZ)

ú¾ (q₀ , ba, baZ)

ú¾ (q₀ , a, bbaZ)

ú¾ (q₀ , e, abbaZ)

(2) (q₀ , abba, Z) ú¾ (q₀ , bba, aZ)

ú¾ (q₀ , ba, baZ)

ú¾ (q₁ , a, aZ)

ú¾ (q₁ , e, Z)

ú¾ (q₂ , e, e)

Так как последовательность (2) оканчивается заключительным состоянием q₂, то МП-автомат R допускает входную цепочку abba. 

В примере 6.2 ясно видна недетерминированная природа МП-автомата R. Для любой конфигурации вида (q₀ , aa, ab) автомат R может сделать один из двух тактов: либо поместить в магазин еще один символ a, либо устранить из магазина верхний символ a.

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

Теперь слегка расширим определение МП-автомата, позволив ему заменять за один такт не только единственный верхний символ магазина, но и цепочку символов ограниченной длины из верхней части магазина другой цепочкой конечной длины.

Расширенным МП-автоматом назовем семерку

R = (Q, S, G, d, q₀, Z₀, F)

где d - отображение конечного подмножества множества Q ´(SÈ{e})´G ^* в множество конечных подмножеств множества Q ´G ^*, а все другие символы имеют тот же смысл, что и раньше.

Конфигурация определяется так же, как и прежде, и мы пишем

(q, aj, ay) ú¾ (q^½, j, by),

если d (q, a, a) содержит (q^½, b), где q, q^½Î Q, aÎ S È {e } и a, b Î G ^*. В этом такте цепочка a, расположенная в верхней части магазина, заменяется цепочкой b. Как и прежде, языком L(R), определяемым автоматом R, называется множество

{w ½ (q₀ , w, Z₀} ú¾ ^* (q, e, b) для некоторых qÎ F и a Î G ^* }

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

Пример 6.3. Определим расширенный МП-автомат R, распознающий язык

L = {aa ^R ½ a Î {a, b} ^* }

Пусть

R = ({q, p}, {a, b}, {a, b, S, Z}, d, q, Z, {p}),

где

(1) d (q, a, e) = {(q, a)}

(2) d (q, b, e) = {(q, b)}

(3) d (q, e, e) = {(q, S)}

(4) d (q, e, aSa) = {(q, S)}

(5) d (q, e, bSb) = {(q, S)}

(6) d (q, e, SZ) = {(p, e)}

На входе aabbaa автомат R может сделать следующую последовательность тактов:

(q, aabbaa, Z) ú¾ (q, abbaa, aZ)

ú¾ (q, bbaa, aaZ)

ú¾ (q, baa, baaZ)

ú¾ (q, baa, SbaaZ)

ú¾ (q, aa, bSbaaZ)

ú¾ (q, aa, SaaZ)

ú¾ (q, a, aSaaZ)

ú¾ (q, a, SaZ)

ú¾ (q, e, aSaZ)

ú¾ (q, e, SZ)

ú¾ (p, e, e)

Работа автомата R состоит в том, что вначале он запасает в магазине некоторый префикс входной цепочки. Затем верхним символом магазина делается маркер S, указывающий предполагаемую середину входной цепочки. Далее R помещает в магазин очередной входной символ и заменяет в магазине aSa или bSb на S. Автомат работает до тех пор, пока не исчерпается вся входная цепочка. Если после этого в магазине останется SZ, то R сотрет SZ и попадет в заключительное состояние. 

Теорема 6.1. Я зык L определяется МП-автоматом тогда и только тогда, когда он определяется расширенным МП-автоматом.

Доказательство. Необходимость условия очевидна, - МП-автомат по определению является расширенным МП-автоматом. Докажем достаточность. Пусть R = (Q, S, G, d, q₀ , Z₀ , F) - расширенный МП-автомат. Тогда существует такой МП-автомат X, что L(X) = L(R).

Положим m = max{½a½ ½ d (q, a, a) ¹ Æ для некоторых qÎ Q, aÎ S È {e } }. Построим МП-автомат X, который будет моделировать автомат R, храня верхние m символов его магазина в “буфере” длины m, занимающем часть конечной памяти управляющего устройства автомата X. Тогда X сможет сказать в начале каждого такта, каковы m верхних символов магазина автомата R. Если в некотором такте R заменяет k верхних символов магазина цепочкой из j символов, то X заменит k первых символов в буфере этой цепочкой длины j. Если j < k, то X сделает k- j вспомогательных e -тактов, в течении которых k- j символов перейдут из верхней части магазина в буфер управляющего устройства. После этого буфер окажется заполненным и X готов моделировать очередной такт автомата. Если j > k, то символы передаются из буфера в магазин.

Итак, положим X = (Q₁ , S, G₁, d₁, q₁ , Z₁ , F₁ ), где

(1) Q₁ = { [q,a ], ½ qÎ Q, a Î G₁ ^*, 0 £ ½a½£ m};

(2) G₁ = G È { Z₁ };

(3) d ₁ определяется так:

(а) Допустим, что d (q, a, X₁ ... X_k ) содержит (r, Y₁ ... Y_j ).

(i) Если j ³ k, то для всех ZÎ G₁ и a Î G₁ ^*, ½a ½= m-k,

d ₁ ([q, X₁ ... X_ka ], a, Z) содержит ([r, b ], g Z)

где bg = Y₁ ... Y_ja и ½b ½= m.

(ii) Если j < k, то для всех ZÎ G₁ и a Î G₁ ^*, ½a ½= m-k,

d ₁ ([q, X₁ ... X_ka ], a, Z) содержит ([r, Y₁ ... Y_ja Z ], e)

(б) Для всех qÎ Q, ZÎ G₁ и a Î G₁ ^*, ½a ½< m,

d ₁ ([q, a ], e, Z) = {([q, a Z ], e)}

Эти правила осуществляют заполнение буфера управляющего устройства, который содержит m символов.

(4) q₁ = [q₀ , Z₀ Z₁ ^m-1 ]. В начальный момент буфер содержит Z₀ наверху и m-1 символов Z₁ пониже. Символы Z₁ используются как специальные маркеры, отмечающие дно магазина

(5) F₁ = {[q, a ] ½ qÎ F, a Î G₁ ^* }.

Непосредственно применяя правила, определяющие X, можно показать, что

(q, aw, X₁ ... X_k X_k+1 ... X_n ) ú¾ _R (r, w, Y₁ ... Y_j X_k+1 ... X_n )

тогда и только тогда, когда

([q, a ], aw, b) ú¾⁺ _X ([r, a ^½ ], w, b ^½),

где

(1) ab = X₁ ... X_n Z₁ ^m,

(2) a^½ b^½ = Y₁ ... Y_j X_k+1 ... X_n Z₁ ^m,

(3) ½a ½=½a^½½= m,

(4) между двумя указанными конфигурациями МП-автомата X нет ни одной конфигурации, состояние которой имело бы вторую компоненту (буфер) длины m.

Таким образом,

(q₀ , w, Z₀ ) ú¾^* _R (q, e, a)

для некоторых qÎ F и a Î G ^* тогда и только тогда, когда

([q₀ , Z₀ Z₁ ^m-1 ], w, Z₁ ) ú¾^* _X ([q, b ], e, g)

где ½b½= m и bg = a Z₁ ^m. Отсюда L(X) = L(R). 

Дата добавления: 2015-06-27