Automat liniar limitat

Un automat liniar mărginit (în engleză linear bounded automata , LBA ) este o anumită mașină Turing nedeterministă în care lungimea benzii este o funcție liniară a dimensiunii intrării. ^[1] Aceste automate sunt capabile să accepte limbaje dependente de context generate de gramaticile contextuale (sau de tipul 1 conform ierarhiei Chomsky ). ^[2] ^[3]

La fel ca o mașină Turing, banda unui LBA este alcătuită din celule care pot conține simboluri aparținând unui alfabet finit . Automatul are un număr finit de stări, iar capul său poate citi și scrie doar o singură celulă la un moment dat.

Gramaticile de tip 1

Același subiect în detaliu: Gramatică dependentă de context .

Singura restricție plasată în gramaticile de tip 1 este că regulile de producție sunt în formă $\alpha \rightarrow \beta$ ${\ displaystyle \ alpha \ rightarrow \ beta}$ ${\ displaystyle \ alpha \ rightarrow \ beta}$ cu $\left|\alpha \right|\leq \left|\beta \right|$ ${\ displaystyle \ left | \ alpha \ right | \ leq \ left | \ beta \ right |}$ ${\ displaystyle \ left | \ alpha \ right | \ leq \ left | \ beta \ right |}$ .

Prin urmare, nicio derivare a unui șir de limbă sensibil la context nu poate conține o formă sentențială care este mai lungă decât șirul în sine. Deoarece există o corespondență unu-la-unu între automatele liniare limitate și aceste gramatici, o bandă mai lungă decât cea ocupată de șirul original nu este necesară pentru recunoașterea șirului de către automat.

Notă

^ Academic Press Dictionary of Science and Technology .
^ (EN) Limbaje formale , în Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
^ (EN) Ierarhia Chomsky , în Encyclopedia of Computer Science, Hoboken, Wiley, 2003.

Bibliografie

(EN) automat mărginit liniar, în Academic Press Dictionary of Science and Technology, Oxford, Elsevier Science & Technology, 1992.

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

[1] Academic Press Dictionary of Science and Technology .

[2] (EN) Limbaje formale , în Encyclopedia of Computer Science, Hoboken, Wiley, 2003.

[3] (EN) Ierarhia Chomsky , în Encyclopedia of Computer Science, Hoboken, Wiley, 2003.

[1]

[2]

[3]