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

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

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

Спољашње везе

• Линеарно ограничени аутомати - Форбс Д. Луис
• Линеарно ограничени аутомати - слајдови, део Контекстно-осетљивих језика Артура Ч. Флека
• Линеарно ограничени аутомати, део Теорије израчунавања слогова Дејвида Матусека