Линеарно-ограничени аутомат

Из Википедије, слободне енциклопедије

Линеарно-ограничени аутомат је недетерминистичка Тјурингова машина са ограничењем. Поседује траку сачињену од ћелија које могу да садрже симболе коначне азбуке, главу која може да чита из једне ћелије или да у њу пише у једном тренутку, и може да се помера дуж траке. Машина поседује коначан број стања. Разликује се од Тјурингове машине по томе иако је трака у старту неограничене дужине, само коначан број узастопних ћелија може да се користи. Број доступних ћелија представља линеарну функцију дужине почетног улаза. Ово ограничење у неким аспектима чини линеарно-ограничени аутомат прецизнијим моделом рачунара који заиста постоје него што је Тјурингова машина.

Линеарно ограничени аутомати су акцептори за класу контекстно-осетљивих језика. Једино ограничење које се поставља за граматику таквих језика је да ниједно правило извођења не може да преслика неку ниску у краћу ниску. Стога ниједно извођење ниске у контекстно-осетљивом језику не може да има реченичну форму дужу од саме ниске. Како постоји један-један пресликавање између линеарно-ограниченог аутомата и таквих граматика, за рад аутомата при препознавању ниске није потребна већа дужина траке од оне потребне за складиштење почетне ниске.

Спољашње везе[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.