Automata Theory 简明教程

Linear Bounded Automata

线性有界自动机是一个多轨非确定性图灵机，其磁带具有某种有界有限长度。

A linear bounded automaton is a multi-track non-deterministic Turing machine with a tape of some bounded finite length.

Length = function (Length of the initial input string, constant c)

Length = function (Length of the initial input string, constant c)

在此，

Here,

Memory information ≤ c × Input information

Memory information ≤ c × Input information

计算受限于常量有界区域。输入字母表包含两个特殊符号，用作左端标记和右端标记，这意味着转换既不会移动到左端标记的左边，也不会移动到磁带右端标记的右边。

The computation is restricted to the constant bounded area. The input alphabet contains two special symbols which serve as left end markers and right end markers which mean the transitions neither move to the left of the left end marker nor to the right of the right end marker of the tape.

线性有界自动机可以定义为 8 元组 (Q, X, ∑, q0, ML, MR, δ, F)，其中 −

A linear bounded automaton can be defined as an 8-tuple (Q, X, ∑, q0, ML, MR, δ, F) where −

  1. Q is a finite set of states

  2. X is the tape alphabet

  3. ∑ is the input alphabet

  4. q0 is the initial state

  5. ML is the left end marker

  6. MR is the right end marker where MR ≠ ML

  7. δ is a transition function which maps each pair (state, tape symbol) to (state, tape symbol, Constant ‘c’) where c can be 0 or +1 or -1

  8. F is the set of final states

linear bounded automata

确定性线性有界自动机总是 context-sensitive ，而空语言线性有界自动机是 undecidable. 。

A deterministic linear bounded automaton is always context-sensitive and the linear bounded automaton with empty language is undecidable..