Automat liniowo ograniczony - Polski Serwis Naukowy

Automat liniowo ograniczony (ang. linear bounded automaton) to 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.

John Hopcroft (ur. 7 października 1939) – amerykański informatyk, ceniony za wkład w rozwój teorii obliczeń, za co (wraz z Robertem Tarjanem) otrzymał nagrodę Turinga w 1986 roku.

Problemem stopu nazywamy sytuację, gdy dla danego algorytmu należy stwierdzić, czy program realizujący dany algorytm zatrzyma się. Pytanie może odnosić się albo do konkretnych danych wejściowych, albo do wszystkich możliwych danych. Jeśli program zatrzymuje się dla wszystkich danych, to mówimy, że ma własność stopu.

Definicja formalna

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

M = (Q, Σ, Г, δ, q0, 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),

q0 – 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:

Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to abstrakcyjna maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa, po przeczytaniu każdego zmieniając swój stan na stan będący wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), słowo należy do języka regularnego, do rozpoznawania którego jest zbudowana.

Niedeterministyczny automat skończony (ang. Non-deterministic Finite-state Automaton, NFA) - maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa. Po przeczytaniu każdego symbolu zmienia ona swój stan na stan będący elementem zbioru, który jest wartością funkcji przejścia. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), mówimy że automat akceptuje czytane słowo.

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.

Tadeusz Krasiński, Automaty i języki formalne, Łódz, Wydawnictwo Uniwersytetu Łódzkiego, 2007 ISBN 978-83-7525-087-9.

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]