Linearno-ograničeni automat
Linearno-ograničeni automat je nedeterministička Tjuringova mašina sa ograničenjem. Poseduje traku sačinjenu od ćelija koje mogu da sadrže simbole konačne azbuke, glavu koja može da čita iz jedne ćelije ili da u nju piše u jednom trenutku, i može da se pomera duž trake. Mašina poseduje konačan broj stanja. Razlikuje se od Tjuringove mašine po tome iako je traka u startu neograničene dužine, samo konačan broj uzastopnih ćelija može da se koristi. Broj dostupnih ćelija predstavlja linearnu funkciju dužine početnog ulaza. Ovo ograničenje u nekim aspektima čini linearno-ograničeni automat preciznijim modelom računara koji zaista postoje nego što je Tjuringova mašina.
Linearno ograničeni automati su akceptori za klasu kontekstno-osetljivih jezika. Jedino ograničenje koje se postavlja za gramatiku takvih jezika je da nijedno pravilo izvođenja ne može da preslika neku nisku u kraću nisku. Stoga nijedno izvođenje niske u kontekstno-osetljivom jeziku ne može da ima rečeničnu formu dužu od same niske. Kako postoji jedan-jedan preslikavanje između linearno-ograničenog automata i takvih gramatika, za rad automata pri prepoznavanju niske nije potrebna veća dužina trake od one potrebne za skladištenje početne niske.
Spoljašnje veze
uredi- Linearno ograničeni automati - Forbs D. Luis
- Linearno ograničeni automati - slajdovi, deo Kontekstno-osetljivih jezika Artura Č. Fleka
- Linearno ograničeni automati Arhivirano na sajtu Wayback Machine (18. januar 2021), deo Teorije izračunavanja slogova Dejvida Matuseka