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

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

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

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

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

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