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, Σ, Г, δ, 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:
w alfabecie taśmy Г są dwa dodatkowe symbole specjalne „<”, „>” które można nazwać lewym i prawym wartownikiem Plik:Automatlinogr1.jpg