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:
Druhým problémem LBA je, zda je třída jazyků přijímaných LBA uzavřena pod komplementem.
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
- ^ 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.
- ^ John Myhill (červen 1960). Lineární ohraničené automaty (technická poznámka WADD). Wright Patterson AFB, Wright Air Development Division, Ohio.
- ^ 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 .
- ^ 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 .
- ^ 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.
- ^ 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
- ^ Szelepcsényi, Róbert (1988), „Metoda vynucování nedeterministických automatů“, Acta Informatica , 26 (3): 279–284
- ^ Arora, Sanjeev; Barak, Boaz (2009). Teorie složitosti: moderní přístup . Cambridge University Press. ISBN 978-0-521-42426-4.
externí odkazy
- Lineární ohraničené automaty podle Forbes D. Lewis
- Snímky lineárních ohraničených automatů , součást kontextově citlivých jazyků od Arthura C. Flecka
- Lineárně vázané automaty , součást osnov Teorie výpočtu, David Matuszek