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

v počítačová věda, a lineárně ohraničený automat (množný lineárně ohraničené automaty, zkráceně LBA) je omezená forma Turingův stroj.

Úkon

Lineárně ohraničený automat je a 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.[1]:225

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í:

  • Jako Turingův stroj, LBA má pásku složenou z buněk, které mohou obsahovat symboly z a konečný abeceda, hlava, která umí číst nebo zapisovat do jedné buňky na pásku najednou a lze ji přesouvat, a konečný počet stavů.
  • LBA se liší od a Turingův stroj v tom, že zatímco páska je zpočátku považována za neomezenou délku, pouze konečná souvislá část pásky, jejíž délka je lineární funkce délky počátečního vstupu je přístupný čtecí / zapisovací hlavou; odtud název lineárně ohraničený automat.[1]:225

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

Silná a slabší definice vede ke stejným výpočetním schopnostem příslušných tříd automatů,[1]:225 v důsledku věta o lineárním zrychlení.

LBA a kontextově citlivé jazyky

Lineární ohraničené automaty jsou akceptory pro třídu kontextově citlivé jazyky.[1]:225–226 Jediné omezení gramatiky pro takové jazyky je to, že žádná produkce nemapuje řetězec na kratší řetězec. Žádná derivace řetězce v kontextu citlivém jazyce tedy nemůže obsahovat a vězeňský formulář 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 John Myhill představil dnes automatový model známý jako deterministický lineárně ohraničený automat.[2] V roce 1963 Peter Landweber prokázal, že jazyky přijímané deterministickými LBA jsou kontextově citlivé.[3] 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.[4][5]

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 tak jako:

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

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)) = spolu-NSPACE(Na))?

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ěď, kterou implikuje Immerman – Szelepcsényiho věta prokázáno 20 let po vzniku problému.[6][7] Ode dneška zůstává první problém s LBA otevřený. Savitchova věta poskytuje počáteční pohled na to NSPACE(O (n)) ⊆ DSPACE(Na2)).[8]

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. ^ P.S. 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 J. M. 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, PAN  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