Razlika između inačica stranice »Linearno ograničen automat«

Trenutačna izmjena od 09:58, 23. ožujka 2022.

Linearno ograničen automat (LOA) (još i omeđeni stroj^[1]) je ograničen oblik nedeterminističkog Turingovog stroja. Posjeduje diskretnu traku koja sadrži znakove (simbole) konačne abecede, pomičnu glavu za čitanje i pisanje koja radi vremenski diskretno, te konačan skup stanja. Razlikuje se od Turingovog stroja u tome što, iako se vrpca na početku smatra beskonačne duljine, samo konačni kontinuirani njezin dio čija je duljina linearno proporcionalna duljini početnog ulaznog niza može čitati/pisati glava za čitanje i pisanje. Ovo ograničenje čini LOA nešto preciznijim modelom stvarnog računala nego Turingov stroj.

Linearno ograničeni automati prihvaćaju klasu kontekstno ovisnih jezika. Jedino ograničenje nad gramatikom takvih jezika jest da ne postoji produkcija koja preslikava niz znakova (string) u kraći niz znakova. Stoga ne postoji produkcija niza znakova u kontekstno ovisnom jeziku koja sadrži rečenični oblik dulji od samog niza. Budući da postoji bijektivna korespondencija između linearno ograničenog automata i takvih gramatika, nije potrebno više vrpce nego što zauzima početni niz znakova da bi sam niz znakova bio prepoznaje linearno ograničeni automat.

Izvori

↑ Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 563

Siniša Srbljić (2003). Jezični procesori 1. Element. ISBN 953-197-129-3

Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva hijerarhija	Gramatike	Jezici	Minimalni automat
Tip 0	Neograničenih produkcija	Rekurzivno prebrojiv	Turingov stroj
n/a	(nema uobičajenog imena)	Rekurzivni	Odlučitelj
Tip 1	Kontekstno ovisna	Kontekstno ovisni	Linearno ograničen
n/a	Indeksirana	Indeksirani	Ugniježđenog stoga
Tip 2	Kontekstno neovisna	Kontekstno neovisni	Nedeterministički potisni
n/a	Deterministička kontekstno neovisna	Deterministički kontekstno neovisni	Deterministički potisni
Tip 3	Regularna	Regularni	Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.

[InfoRjecnik-1] Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 563

[1]

Inačica od 06:13, 17. studenoga 2021. (vidi izvor) WikiSysop (razgovor \| doprinosi) m (Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)) ← Starija izmjena		Trenutačna izmjena od 09:58, 23. ožujka 2022. (vidi izvor) WikiSysop (razgovor \| doprinosi) m (bnz)
Redak 1:		Redak 1:
	~~<!--'''Linearno ograničen automat'''-->'''~~Linearno ograničen automat''' (LOA) (još i '''omeđeni stroj'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 563</ref>) je ograničen oblik [[nedeterministički Turingov stroj\|nedeterminističkog Turingovog stroja]]. Posjeduje diskretnu traku koja sadrži znakove (simbole) konačne [[abeceda (računarstvo)\|abecede]], pomičnu glavu za čitanje i pisanje koja radi vremenski diskretno, te konačan skup stanja. Razlikuje se od Turingovog stroja u tome što, iako se vrpca na početku smatra beskonačne duljine, samo konačni kontinuirani njezin dio čija je duljina linearno proporcionalna duljini početnog ulaznog niza može čitati/pisati glava za čitanje i pisanje. Ovo ograničenje čini LOA nešto preciznijim modelom stvarnog [[računalo\|računala]] nego Turingov stroj.		Linearno ograničen automat''' (LOA) (još i '''omeđeni stroj'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 563</ref>) je ograničen oblik [[nedeterministički Turingov stroj\|nedeterminističkog Turingovog stroja]]. Posjeduje diskretnu traku koja sadrži znakove (simbole) konačne [[abeceda (računarstvo)\|abecede]], pomičnu glavu za čitanje i pisanje koja radi vremenski diskretno, te konačan skup stanja. Razlikuje se od Turingovog stroja u tome što, iako se vrpca na početku smatra beskonačne duljine, samo konačni kontinuirani njezin dio čija je duljina linearno proporcionalna duljini početnog ulaznog niza može čitati/pisati glava za čitanje i pisanje. Ovo ograničenje čini LOA nešto preciznijim modelom stvarnog [[računalo\|računala]] nego Turingov stroj.

	Linearno ograničeni automati prihvaćaju klasu [[kontekstno ovisni jezik\|kontekstno ovisnih jezika]]. Jedino ograničenje nad [[gramatika\|gramatikom]] takvih jezika jest da ne postoji produkcija koja preslikava niz znakova (string) u kraći niz znakova. Stoga ne postoji produkcija niza znakova u kontekstno ovisnom jeziku koja sadrži rečenični oblik dulji od samog niza. Budući da postoji bijektivna korespondencija između linearno ograničenog automata i takvih gramatika, nije potrebno više vrpce nego što zauzima početni niz znakova da bi sam niz znakova bio prepoznaje linearno ograničeni automat.		Linearno ograničeni automati prihvaćaju klasu [[kontekstno ovisni jezik\|kontekstno ovisnih jezika]]. Jedino ograničenje nad [[gramatika\|gramatikom]] takvih jezika jest da ne postoji produkcija koja preslikava niz znakova (string) u kraći niz znakova. Stoga ne postoji produkcija niza znakova u kontekstno ovisnom jeziku koja sadrži rečenični oblik dulji od samog niza. Budući da postoji bijektivna korespondencija između linearno ograničenog automata i takvih gramatika, nije potrebno više vrpce nego što zauzima početni niz znakova da bi sam niz znakova bio prepoznaje linearno ograničeni automat.