8.6. Lineárisan korlátozott automata

A következőkben egy másik, a szakirodalom által jól ismert olyan automata modellt mutatunk be, amely pontosan a környezetfüggő nyelveket fogadja el. A lineárisan korlátolt automatának (Linear Bounded Automaton (LBA), vagy lineárisan korlátozott Turing-gép) több változata is ismert, ezek közül ismertetünk egyet. Az automata egy véges vezérlővel rendelkezik és egy szalaggal, amelyen kezdetben az input szó áll. Az automata a működése során két lényeges eltérést mutat az eddig tárgyalt automatákhoz képest: az egyik, hogy a szalagon a fej előre és hátra is mozoghat, a másik, még lényegesebb, hogy nem csak olvashatja a szalagot, de annak tartalmát át is írhatja, ennek megfelelően nem olvasó, hanem író-olvasó fejről beszélünk.

23. Definíció. Az L B A=(Q, T, V, q 0, #, d, F)- t (nemdetrminisztikus) lineárisan korlátozott automatának hívjuk, ha Q az állapotok véges halmaza, T az inputábécé, VT a szalagábécé, q 0 a kezdőállapot, #∈V\T speciális jel a szalag azon részén, ahol nincs input (tulajdonképpen a szóköz jelnek feleltethető meg), d az átmenetfüggvény, FQ pedig a végállapotok halmaza. A d átmenetfüggvény (leképezés) alakja a következő: a (Q×(V∖{#})) halmazból képez a (Q×V×{B a l, J o b b, H e l y b e n}) részhalmazaiba, illetve (Q×{#}) halmazból képez a (Q×#×{B a l, J o b b, H e l y b e n}) részhalmazaiba. ★

Az automata egy konfigurációját (u, q, a v) –ként írhatjuk le, ahol u, vV * a szalagon levő információ a fejtől balra, illetve jobbra, qQ az aktuális állapot, aV pedig a fej által éppen látott szimbólum a szalagon. Kezdetben az input # jelek között szerepel az input szalagon és a fej az input első betűjére van pozícionálva, vagyis a kezdeti konfiguráció (λ, q 0, a w ') ahol az input w=a w '. (Üresszó input esetén (λ, q 0, #) a konfiguráció kezdetben.)

Az automata vezérlője (a d leképezés által leírt módon) az aktuális állapot és az éppen olvasott szimbólum alapján nemdeterminisztikusan választ a lehetséges átmenetek közül: (q ', b, m)∈d(q, a) jelentése: ha az automata q állapotban van és a szimbólumot lát a szalagon, akkor átmehet q ' állapotba, miközben a szalagon a helyére b- t ír és a fej az m∈{B a l, J o b b, H e l y b e n} által megadott irányba lép egyet a szalagon (vagy értelemszerűen Helyben esetén helyben marad). Akkor mondjuk, hogy az automata elfogadott egy input szót, ha van az átmeneteknek olyan véges sorozata a szó feldolgozása során, hogy az automata végállapotba jut. Az elfogadott szavak halmaza adja az elfogadott (vagy felismert) nyelvet.

A definícióból látható, hogy a szalagon levő # jelek nem írhatóak felül, ennek megfelelően az automata csak az eredeti input által elfoglalt területet használhatja számolásra.

67. Tétel. A lineárisan korlátozott automatákkal elfogadott nyelvek osztálya megegyezik a környezetfüggő nyelvek osztályával.

A bizonyítás ötletét röviden mutatjuk be: Ha egy nyelv környezetfüggő, akkor monoton nyelvtannal generálható, vagyis a mondatforma hossza a levezetés egyik lépésében sem haladja meg a levezett szó hosszát. Az adott nyelvtan alapján megszerkeszthető egy olyan lineárisan korlátozott automata, amely éppen a szabályok alkalmazását szimulálja visszafelé. Ha adott egy lineárisan korlátozott automata, akkor készíthető egy olyan analitikus nyelvtan, amely pont az automatát szimulálja, a nemterminális éppen a fej helyét jelöli, és tárolja az aktuális állapotot. Ez alapján a duális, generatív nyelvtan is elkészíthető, ami monoton. ∎

Itt jegyezzük meg, hogy a nemdeterminisztikus lineárisan korlátozott automata az amely a környezetfüggő nyelvosztály elfogadására alkalmas, az pedig, hogy a determinisztikus lineárisan korlátozott automaták által felismert nyelvek osztálya valódi részhalmaza-e ennek egy e jegyzet megírása idején is fennálló nevezetes megoldatlan probléma.

Igazolható, hogy az ismertetett modellel ekvivalensek, vagyis ugyanezt a nyelvosztályt fogadják el azok a lineárisan korlátozott automaták, ahol az automatának egy előre rögzített k konstansszor annyi szalagpozíció (tárhely) áll rendelkezésre működése során, mint az input hossza (lásd Tárhely tétel). Továbbá az is ismert (Savitch tétele (ejtsd: szévics)), hogy determinisztikus automatával, négyzetesen korlátolt tárral (vagyis, ahol az inputszó hosszának négyzetével arányos a megengedetten felhasználható szalagterület) minden környezetfüggő nyelv felismerhető.