linear_bounded.md

Linear Bounded Automata

Definition

Formal

• 5 tuple (Q, Σ, Γ, q0, δ)
  • Q is finite state of inputs
  • Σ is alphabet
  • Γ is tape input
  • (δ: Q x (Γ ∪ {,}) -> Q x (Γ ∪ {,} x A)) is the transition function

Informal

• Has memory in the form of a finite tape.
• At each step LBA can perform an action where action = {Y,N,L,R}
  • Y = Yes
  • N = No
  • L = Keft
  • R = Right

Transitions

In Linear Bounded Automata a transition looks like:

(p, a) -> (q, b, A)

• p is original state
• a is at current read/write position
• q is new state
• b is now at current read/write position
• A is the action that is performed where A ∈ {L,R,Y,N}

Example

L(G) = { (a^n b^n c^n) |n ≥ 1}

Q = {s, t, u, v,w}
Σ = {a, b, c}
Γ = {a, b, c, x}
q0 = s
δ = {
    ((s, [),(t, [, R)),((t, ]),(t, ],Y )),((t, x),(t, x, R)),
    ((t, a),(u, x, r)),((u, a),(u, a, R)),((u, x),(u, x, R)),
    ((u, b),(v, x, R))((v, b),(v, b, R)),((v, x),(v, x, R)),
    ((v, c),(w, x, L))((w, c),(w, c, L)),((w, b),(w, b, L)),
    ((w, a),(w, a, L))((w, x),(w, x, L)),((w, [),(t, [, R))
}