Automat liniowo ograniczony

Automat liniowo ograniczony (ang. linear bounded automaton) – ograniczona wersja maszyny Turinga, która podczas obliczenia na słowie wejściowym długości n może wykorzystać jedynie O(n) komórek taśmy. Innymi słowy, dostępna pamięć jest funkcją liniową od długości wejścia. Można także powiedzieć, że może ona w trakcie działania wykorzystywać tylko te komórki na taśmie, w których zapisane jest słowo wejściowe.

Definicja formalna

Formalnie automatem liniowo ograniczonym nazywamy jednotaśmową maszynę Turinga z własnością stopu:

M = (Q, Σ, Г, δ, q₀, B, F) gdzie:

• Q – zbiór skończony, którego elementy nazywamy stanami M,
• Σ – zbiór skończony, zwany alfabetem M,
• Γ – zbiór skończony, zwany alfabetem taśmy M, taki że Σ ⊂ Γ,
• δ : D → Q x Γ x {L,R}, gdzie D jest pewnym podzbiorem Q x Г (δ nazywamy funkcją przejść lub ruchów M),
• q₀ – wyróżniony stan, zwany stanem początkowym M,
• B – wyróżniony symbol, zwany symbolem pustej komórki,
• F ⊂ Q – wyróżniony podzbiór stanów, zwanych stanami końcowymi M.

dla której spełnione są poniższe warunki:

• w alfabecie taśmy Г są dwa dodatkowe symbole specjalne „<”, „>” które można nazwać lewym i prawym wartownikiem

• początkowe ruchy M to umieszczanie symbolu „<” na początku słowa wejściowego i symbolu „>” na jego końcu. Następnie głowica przesuwa się na początek słowa wejściowego:

• M nie ma ruchów przesuwających głowicę w lewo od symbolu „<” i w prawo od symbolu „>” (dane wejściowe są zapisane na taśmie maszyny między symbolami – wartownikami).

W opisie automatów liniowo ograniczonych zwykle pomijamy pierwsze formalne ruchy umieszczające symbole „<” i „>” na krańcach słowa. Podajemy tylko dalsze istotne ruchy.

• symbole „<”, „>” nie mogą zmieniać innych symboli ani być zamienione na inne z wyjątkiem samych siebie, czyli nie można zapisywać ich do innych komórek niż ograniczające odcinek taśmy przeznaczony do obliczeń.

Języki akceptowalne przez automaty liniowo ograniczone

Automaty liniowo ograniczone są ograniczonymi modelami jednotaśmowych maszyn Turinga, zatem klasa języków akceptowalnych przez automaty liniowo ograniczone zawiera się w klasie maszyn Turinga z własnością stopu.

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:

Bibliografia

• Władysław Homenda, Elementy lingwistyki matematycznej i teorii automatow, Warszawa, Oficyna wydawnicza Politechniki Warszawskiej, 2005 ISBN 83-7207-503-4.
• TadeuszT. Krasiński TadeuszT., Automaty i języki formalne, Łódź: Wydawnictwo Uniwersytetu Łódzkiego, 2007, ISBN 978-83-7525-087-9, OCLC 749791224 .
• J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Warszawa, „Wydawnictwo Naukowe PWN”, 2005 ISBN 83-01-14502-1.

Linki zewnętrzne

• Wykład – Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga: [1]