Linearno ograničen automat

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

Linearno ograničen automat (LOA) je ograničen oblik nedeterminističkog Turingovog automata. Posjeduje diskretnu traku koja sadrži znakove (simbole) konačne abecede, pomičnu glavu za čitanje i pisanje koja operiše vremenski diskretno, te konačan skup stanja. Razlikuje se od Turingove mašine u tome što, iako se traka na početku smatra beskonačne dužine, samo konačni kontinuirani njezin dio čija je dužina linearno proporcionalna dužini početnog ulaznog niza se može čitati/pisati od strane glave za čitanje i pisanje. Ovo ograničenje čini LOA nešto preciznijim modelom stvarnog računara nego Turingova mašina.

Linearno ograničeni automati prihvataju klasu kontekstno zavisnih 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 zavisnom jeziku koja sadrži rečenični oblik duži od samog niza. Budući da postoji bijektivna korespondencija između linearno ograničenog automata i takvih gramatika, nije potrebno više trake nego što zauzima početni niz znakova da bi sam niz znakova bio prepoznat od strane linearno ograničenog automata.