Lineárně ohraničený automat - Linear bounded automaton

V informatice je lineárně ohraničený automat (množné číslo lineárně ohraničené automaty , zkráceně LBA ) omezenou formou Turingova stroje .

Úkon

Lineárně ohraničený automat je nedeterministický Turingův stroj, který splňuje následující tři podmínky:

  • Jeho vstupní abeceda obsahuje dva speciální symboly, které slouží jako levý a pravý koncový znak.
  • Jeho přechody nemusí vytisknout jiné symboly nad koncovými značkami.
  • Jeho přechody se nemusí pohybovat nalevo od levého koncového ukazatele ani napravo od pravého koncového ukazatele.

Jinými slovy: namísto potenciálně nekonečné pásky, na které se počítá, je výpočet omezen na část pásky obsahující vstup plus dva čtverce pásky, které drží endmarkery.

Alternativní, méně omezující definice je následující:

  • Stejně jako Turingův stroj má LBA pásku složenou z buněk, která může obsahovat symboly z omezené abecedy , hlavu, která umí číst nebo zapisovat do jedné buňky na pásku najednou a lze ji přesouvat, a konečný počet státy.
  • LBA se liší od Turingova stroje v tom, že zatímco se na pásce zpočátku předpokládá, že má neomezenou délku, čtecí / přístupná je přístupná pouze konečná souvislá část pásky, jejíž délka je lineární funkcí délky počátečního vstupu. zapisovací hlava; odtud název lineárně ohraničený automat .

Toto omezení dělá z LBA poněkud přesnější model počítače v reálném světě než Turingův stroj, jehož definice předpokládá neomezenou pásku.

Silná a slabší definice vede ke stejným výpočtovým schopnostem příslušných tříd automatů díky teorému o lineárním zrychlení .

LBA a kontextově citlivé jazyky

Lineární ohraničené automaty jsou akceptory pro třídu kontextově citlivých jazyků . Jediným omezením pro gramatiky pro takové jazyky je, že žádná produkce nemapuje řetězec na kratší řetězec. Žádná derivace řetězce v kontextu citlivém jazyce tedy nemůže obsahovat větnou formu delší než samotný řetězec. Vzhledem k tomu, že mezi automaty s lineárním ohraničením a takovými gramatikami existuje vzájemná korespondence, není pro automatický rozpoznávání řetězce nutná žádná páska než ta, která je obsazena původním řetězcem.

Dějiny

V roce 1960 představil John Myhill automatický model, dnes známý jako deterministický lineárně ohraničený automat. V roce 1963 Peter Landweber dokázal, že jazyky přijímané deterministickými LBA jsou kontextově citlivé. V roce 1964, S.-Y. Kuroda představil obecnější model (nedeterministických) lineárních ohraničených automatů, poznamenal, že Landweberův důkaz funguje také pro nedeterministické lineární ohraničené automaty, a ukázal, že jimi přijímané jazyky jsou přesně kontextově citlivými jazyky.

Problémy s LBA

Ve své seminární práci Kuroda rovněž uvedl dvě výzkumné výzvy, které se následně proslavily jako „problémy LBA“: Prvním problémem LBA je, zda se třída jazyků přijímaných LBA rovná třídě jazyků přijímaných deterministickým LBA. Tento problém lze stručně formulovat v jazyce teorie výpočetní složitosti jako:

První problém s LBA : Je NSPACE (O (n)) = DSPACE (O (n))?

Druhým problémem LBA je, zda je třída jazyků přijímaných LBA uzavřena pod komplementem.

Druhý problém LBA : Je NSPACE (O (n)) = co- NSPACE (O (n))?

Jak již uvedl Kuroda, negativní odpověď na druhý problém LBA by znamenala negativní odpověď na první problém. Ale druhý problém LBA má kladnou odpověď, což vyplývá z Immerman-Szelepcsényiho věty prokázané 20 let poté, co byl problém nastolen. Ode dneška zůstává první problém s LBA otevřený. Savitchova věta poskytuje počáteční vhled, že NSPACE (O (n)) ⊆ DSPACE (O (n 2 )).

Reference

  1. ^ a b c d John E. Hopcroft ; Jeffrey D. Ullman (1979). Úvod do teorie automatů, jazyků a výpočtu . Addison-Wesley. ISBN 978-0-201-02988-8.
  2. ^ John Myhill (červen 1960). Lineární ohraničené automaty (technická poznámka WADD). Wright Patterson AFB, Wright Air Development Division, Ohio.
  3. ^ PS Landweber (1963). "Tři věty o frázových strukturních gramatikách typu 1" . Informace a kontrola . 6 (2): 131–136. doi : 10,1016 / s0019-9958 (63) 90169-4 .
  4. ^ Sige-Yuki Kuroda (červen 1964). "Třídy jazyků a lineárně ohraničené automaty" . Informace a kontrola . 7 (2): 207–223. doi : 10,1016 / s0019-9958 (64) 90120-2 .
  5. ^ Willem JM Levelt (2008). Úvod do teorie formálních jazyků a automatů . Nakladatelství John Benjamins. str. 126–127. ISBN 978-90-272-3250-2.
  6. ^ Immerman, Neil (1988), „Nedeterministický prostor je uzavřen doplňováním“ (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi : 10.1137 / 0217058 , MR  0961049
  7. ^ Szelepcsényi, Róbert (1988), „Metoda vynucování nedeterministických automatů“, Acta Informatica , 26 (3): 279–284
  8. ^ Arora, Sanjeev; Barak, Boaz (2009). Teorie složitosti: moderní přístup . Cambridge University Press. ISBN 978-0-521-42426-4.

externí odkazy