Linjärt begränsad automat

Inom datavetenskap är en linjär avgränsad automat (plural linjär avgränsad automat , förkortad LBA ) en begränsad form av Turing-maskin .

Drift

En linjär avgränsad automat är en icke-deterministisk Turing-maskin som uppfyller följande tre villkor:

  • Dess inmatningsalfabet innehåller två speciella symboler, som fungerar som vänster och höger slutmarkörer.
  • Dess övergångar får inte skriva ut andra symboler över ändmarkörerna.
  • Dess övergångar får varken flyttas till vänster om den vänstra ändmarkören eller till höger om den högra ändmarkören.

Med andra ord: istället för att ha ett potentiellt oändligt band att beräkna på, är beräkningen begränsad till den del av bandet som innehåller ingången plus de två bandrutorna som håller slutmarkörerna.

En alternativ, mindre restriktiv definition är följande:

  • Liksom en Turing-maskin har en LBA ett band som består av celler som kan innehålla symboler från ett ändligt alfabet , ett huvud som kan läsa från eller skriva till en cell på bandet åt gången och kan flyttas, och ett ändligt antal stater.
  • En LBA skiljer sig från en Turing-maskin genom att medan bandet initialt anses ha obegränsad längd, kan endast en ändlig angränsande del av bandet, vars längd är en linjär funktion av längden på den initiala ingången, nås av läs/ skrivhuvud; därav namnet linjärt avgränsad automat .

Denna begränsning gör en LBA till en något mer exakt modell av en verklig dator än en Turing-maskin, vars definition förutsätter obegränsat band.

Den starka och den svagare definitionen leder till samma beräkningsförmåga hos respektive automatklass, med samma argument som används för att bevisa den linjära speedup-satsen .

LBA och sammanhangskänsliga språk

Linjära avgränsade automater är acceptorer för klassen av sammanhangskänsliga språk . Den enda begränsningen för grammatik för sådana språk är att ingen produktion mappar en sträng till en kortare sträng. Således kan ingen härledning av en sträng i ett sammanhangskänsligt språk innehålla en meningsform längre än själva strängen. Eftersom det finns en en-till-en-överensstämmelse mellan linjära automater och sådana grammatiker, behövs inte mer band än det som upptas av originalsträngen för att strängen ska kännas igen av automaten.

Historia

År 1960 introducerade John Myhill en automatmodell idag känd som deterministisk linjärbegränsad automat. 1963 Peter Landweber att de språk som accepteras av deterministiska LBA är kontextkänsliga. År 1964 har S.-Y. Kuroda introducerade den mer generella modellen för (icke-deterministiska) linjära gränsade automater, och anpassade Landwebers bevis för att visa att språken som accepteras av icke-deterministiska linjära gränsade automater är just de kontextkänsliga språken.

LBA-problem

Kuroda angav i sin framträdande artikel också två forskningsutmaningar, som senare blev kända som "LBA-problemen": Det första LBA-problemet är om klassen av språk som accepteras av LBA är lika med klassen av språk som accepteras av deterministisk LBA. Detta problem kan formuleras kortfattat på beräkningskomplexitetsteorins språk som:

Första LBA-problemet : Är NSPACE (O( n )) = DSPACE (O( n ))?

Det andra LBA-problemet är om klassen av språk som accepteras av LBA är stängd under komplement.

Andra LBA-problemet : Är NSPACE (O( n )) = co- NSPACE (O( n ))?

Som redan observerats av Kuroda skulle ett negativt svar på det andra LBA-problemet innebära ett negativt svar på det första problemet. Men det andra LBA-problemet har ett jakande svar, vilket antyds av Immerman-Szelepcsényi-teoremet som bevisades 20 år efter att problemet togs upp. Från och med idag är det första LBA-problemet fortfarande öppet. Savitchs teorem ger en första insikt, att NSPACE (O( n )) ⊆ DSPACE (O( n 2 )).

  1. ^ a b c d   John E. Hopcroft ; Jeffrey D. Ullman (1979). Introduktion till automatteori, språk och beräkningar . Addison-Wesley. ISBN 978-0-201-02988-8 .
  2. ^ John Myhill (juni 1960). Linear Bounded Automata (WADD Technical Note). Wright Patterson AFB, Wright Air Development Division, Ohio.
  3. ^ PS Landweber (1963). "Tre satser om frasstrukturgrammatik av typ 1" . Information och kontroll . 6 (2): 131–136. doi : 10.1016/s0019-9958(63)90169-4 .
  4. ^ Sige-Yuki Kuroda (juni 1964). "Klasser av språk och linjärt avgränsade automater" . Information och kontroll . 7 (2): 207–223. doi : 10.1016/s0019-9958(64)90120-2 .
  5. ^   Willem JM Levelt (2008). En introduktion till teorin om formella språk och automater . John Benjamins förlag. s. 126–127. ISBN 978-90-272-3250-2 .
  6. ^   Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi : 10.1137/0217058 , MR 0961049
  7. ^   Szelepcsényi, Róbert (1988), "The method of force for nondeterministic automata", Acta Informatica , 26 (3): 279–284, doi : 10.1007/BF00299636 , S2CID 10838178
  8. ^   Arora, Sanjeev ; Barak, Boaz (2009). Complexity Theory: A Modern Approach . Cambridge University Press. ISBN 978-0-521-42426-4 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Linear_bounded_automaton&oldid=1130857022 "