Równość klas automatów liniowo ograniczonych deterministycznych i niedeterministycznych jest problemem otwartym. Wiadomo, że można znaleźć automat deterministyczny symulujący obliczenie automatu niedeterministycznego taki, że długość taśmy, na której prowadzi obliczenie jest funkcją kwadratową długości taśmy, na której prowadzi obliczenie automat niedeterministyczny.
Klasa języków rozpoznawanych przez automaty liniowo ograniczone to dokładnie języki kontekstowe.
Język formalny L nazywamy ALO – kontekstowym, gdy istnieje automat liniowo ograniczony M taki, że L = L(M).
Język akceptowany przez automat liniowo ograniczony jest jednym z czterech typów pokazanych w tabeli:
Gramatyka Inna nazwa Język AutomatTypu 0GFJRPMTTypu 1GKJKALOTypu 2GBKJBKAZSTypu 3GRJRDAS, NAS, NAS-Λ
Bibliografia Władysław Homenda, Elementy lingwistyki matematycznej i teorii automatow, Warszawa, Oficyna wydawnicza Politechniki Warszawskiej, 2005 .
J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Warszawa, „Wydawnictwo Naukowe PWN”, 2005 .
Linki zewnętrzne Wykład – Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga:
Kategoria:Teoria automatów