Главная Промышленная автоматика.

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

В данном случае заметим, что если Р допускает непустую цепочку, то он доллен пройти через состояния ц, gr, q, q именно в этом порядке.

Далее, если [qw, Z)\- (qi,e, а) д,ля \, то w=0 naOZ. Аналогично, если ((?а, ix), а) - {з, е, р), то ау= 1* и а -Оф. К тому же а) [- (?2» Р) только тогда, когда w= 1 и аор,

а (q.,w, Z)\-* {q(,ye, е) только тогда, когда = е. Таким образом, -если (qQ,w, Z)\- {qa, е,а) для некоторого £0, то либо w = e и / - О, либоЕОЧ", I 2п + U " а=е. Следовательно, L ЦР). П

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

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

Пусть РЦдодд}, {а,Ь}, {Z,a,b}, &,qt,,Z, {q}), где

(1) &{q,,a,Z){(q,aZ)}

(2) 6{q,,b,Z){{q„bZ)}

(3) 6(9„,Q, a)-{(,.aa), (qe)}

(4) 6(9„a,&){p,a&)}

(5) 6{q,,b,a){{q,,,ba)\

(6) 6{q,,b,b){{q,,bb), (?,е)}

(7) b{q,a, a) = {(9„e)}

(8) 6(9i,b, 6) = {(?i,e)}

(9) d(qi,e,Z) = {{q,,e)}

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

ним (и единственным) символом магазина, то по правилу (9) Р стирает Z и попадает в состояние q. Итак, Р допускает цепочку тогда и только тогда, когда все сравнения обнаружили совпадение символов.

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

(1) {q„ abba, Z)\-[q,, bba, aZ)

y-iqba, baZ) \-{q,a,bbaZ) 1- (0. abbaZ)

(2) (0, abba, Z) y- [q, bba, aZ)

H (q, ba, baZ) I- [q, a, aZ)

H (Яь Z) l-C/a.e.e)

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

Как и раньше, относительно легко показать, что если w= сс.. .ccc.i.. .Ci, где Ci{a,b} для то

(Яо, W, Z) Vn-i •••ь <rfin-i • •

Н"- (ЯъЛ)

Таким образом, LL(P).

Несколько труднее доказать, что если (?о> » Ж* (/а» сс) для некоторого а g Г*, то wxx для некоторого х(а+ЬУ и ае. Оставляем доказательство в качестве упражнения и, считая это утверждение истинным, заключаем, что L(P)=L. □

В примере 2.32 ясно видна недетерминированная природа МП-автомата Р. Для любой конфигурации вида (qQ,aw,aa) автомат Р может Сделать один из двух тактов: либо поместить в магазин еще один символ а, либо устранить из магазина верхний символ а.

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



2.5.2. Варианты МП-автоматов

В этом разделе мы определим некоторые варианты понятия МП-автомата и установим связь между определяемыми ими языками и языками, определяемыми МП-автоматами в смысле первоначального определения. Но сначала нам хотелось бы выявить один фундаментальный аспект поведения МП-автомата, который интуитивно представляется совершенно ясным. Его можно сформулировать так: „То, что происходит с верхним символом магазина, не зависит от того, что находится в магазине под ним".

Лемма 2.20. Пусть P = (Q,2,T,b,q(,ZQ,F)-}A-aemoMam. Если {д, Л) Н" {ду е, е), то (д, w, Аа) -" {д\ е, а) для всех Л С Г и а 6 Г*.

Доказательство. Доказательство индукцией по п довольно элементарно. Для ri = l лемма, очевидно, верна. Допустим, что она верна для всех {п<п, и пусть {q,w, А)\-"{д,е,е). Тогда соответствующая последовательность тактов должна иметь вид

{g,w,A)\ {g,,w„X,...X,) Ь" {g,,w,,X,,..X„)

{д\е,е)

где й>1 и П1<п для

Тогда для любых а С Г* также возможна последовательность (д, W, Аа) h- Х. - -Ха)

Ь"» {q2w„X.,...X„a)

2.5. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

[-"k-i{qk,Wk, Xfa) {q,e,a)

1) Это еще один пример „очевидного" утверждения, которое может ио-требопать некоторого размышления. Представьте себе МП-автомат, проходящий указанную последовательность конфигураций. Рано или поздно длина магазинной цепочки впервые станет равной А:-I. Так как ни один из символов Xg.-.Xft не был верхним символом магазина, они так и останутся в нем, так что «1 - число сделанных к этому моменту тактов. Затем ждем, когда длина магазина впервые станет равной /г -2, н берем в качестве число дополнн- тельио потребовавшихся тактов. Продолжаем в том же духе, пока магазин не станет пустым.

Всюду, кроме первого такта, мы пользовались здесь предположением индукции. □

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

Определение. Расширенным МП-автоматом назовем семерку Р - (Q, 2, Г, 6, Zp, f), где б -отображение конечного подмножества множества Qx(2U{e})xr* в множество конечных подмножеств множества QxF*, а все другие с]змволы имеют тот же смысл, что и раньше.

Конфигурация определяется так же, как прежде, и мы птг-шем {д, aw, ау) \-{q,w,y), если 6{q,a,a) содержит (<?, р), где q£Q> a£t[j{e\ и аГ*. В этом такте цепочка а, расположенная в верхней части магазина, заменяется цепочкой р. Как и прежде, языком L(P), определяемым автоматом Р, называется множество

{w\{qf,w,Z)\-* (q,e,a) для некоторых qF и а g Г*}

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

Пример 2.33. Определим расширенный МП-автомат Р, распознающий язык {ww\w£{a,b)]. Пусть Р {{q, р), {a,b), {a,b,S,Z},b,q,Z, {р}), где

(1) б(9,а, е) ={iq,a)}

(2) 8{q,b, е) =-{{q,b)} (3)6(,6, е) ={{g,S)}

(4) b{q,e,aSa){{q,S)}

(5) 6(q,e,bSb){{q,S)\

(6) b{q,e, SZ) = {ip,e)}

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

{q, aabbaa, Z) Н {q, abbaa, aZ)

1-{q, bbaa, aaZ)

\~- [q, baa, bauZ)

\~- {q, baa, SbaaZ)

- ((?, aa, bSbaaZ)



2.5. птолдАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

- (9, аа, SaaZ) [- ((?, а, aSaaZ) \-(q,a,SaZ) \- (q, е, aSaZ) \-{q,e,SZ)

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

Покажем, что язык L определяется МП-автоматом тогда и только тогда, когда оп определяется расширенным МП-автоматом. Необходимость условия очевидна; докажем достаточность.

Лемма 2.21. Пусть Р - (Q, S, Г, б, q, 2, F)-расширенный МИ-автолшт. Тогда существует такой МП-автолшт Р, что L(P,)L(P).

Доказательство. Положим т = max { а 11 б о, а) Ф0 для некоторых qQ, aS.\j{e]}. Построим МП-автомат Pj, который будет моделировать автомат Р, храня верхние т символов его магазина в „буфере" длины т, занимающем часть конечной памяти управляющего устройства автомата Pj. Тогда Pj сможет сказать в начале каждого такта, каковы т верхних символов магазина автомата Р. Если в некотором такте Р заменяет k верхних символов магазина цепочкой нз / символов, то Pj заменит к первых символов в буфере этой цепочкой длины /. Если / < fe, то Pf сделает k - / вспомогательных -тактов, в течение которых k - / символов перейдут из верхней части магазина в буфер управляющего устройства. После этого буфер окажется заполненным, и Pj готов моделировать очередной такт автомата Р. Если / > /г, то символы передаются из буфера в магазин.

Итак, положим Pi (Qi, 2, Г,, 6j, i, Z, р), где

(1) Q,r={[q,a] qQ, aTl 0<a</n};

(2) TirulZ,};

(3) 6i определяется так:

(a) Допустим, что б(, a, X.. .Х) содержит {r,V...V). (i) Если ife, то длявсех2€Г1 и aTl,\a\==m-k,

Л[ЯХ. ,.Xjfq,a,Z) содержит ([г,р], у2)

где ру = Kj... KfCt и 1 р 1 = m.

(ii) Если К к, то для всех ZTj и а€П, а==т-/г, 6i([g,Xi...Xfca],a,Z) содержит ([г, Kj.. .KaZ], е) (б) Для всех qQ, ZT и аП. 1а<т, 6,([q, а], Z) =={([?, aZ], е)}

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

(4) А, -[i/o.Z(,Zf-]. В начальный момент буфер содержит Zq наверху и т-1 символов Z попиже. Символы Z используются как специальные маркеры, отмечающие ,дно", т. е, нижний конец магазина

(5) E,{[q,]\qeF, а€П}.

Нетрудно показать, что

{q, aw, X,... ХЛ. .. XJ Hp (г. , П... КД!... Х„) тогда и только тогда, когда ([, а], aw, Р) [-р, ([г, а], w,), где

(1) ap = Xi..-X„Z-

(2) aP-K,...y.,,...X„Zr,

(3) \а\\а\=т,

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

Для этого достаточно непосредственно применить правила,

определяющие Р.

Таким образом, ((?„» Z) -р (q, а) для некоторых qF и аГ* тогда и только тогда, когда

{[q„Z,Zrl W, Zj)h-K([<?.PL Т) где р = т и PvoZl" Отсюда 1(Р)=1(Р), □

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

Определение. Пусть P - (Q, 2, Г, 6, д, Z, Р)-МП-автомат или расширенный МП-автомат. Будем говорить, что Р допускает цепочку ггб2* опустоьиением магазина, если (д» о) ]-(9, , ) для некоторого qQ. Пусть Z,(Р)-множество цепочек, допускаемых автоматом Р опустошением магазина.

Лемма 2.22. Пусть L=L{P) для некоторого МП-ттомата P = {Q, S, Г, б, Zo, F). Мооюно построить такой МП-автомат Р\ что L,{P)L,

Доказательство. Пусть Р моделирует Р. Всякий раз, Когда Р переходит в заключительное состояние, Р решает, про-





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 [32] 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0035