Википедија

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

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Линеарно-ограничени_аутомат&oldid=26918791”