![]() |
|
Главная Промышленная автоматика. же, как для грамматик, гораздо труднее доказать, что он допускает цепочки только определенного вида. В данном случае заметим, что если Р допускает непустую цепочку, то он доллен пройти через состояния ц, 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.0019 |