文脈依存言語
計算性という観点では、文脈依存言語は線形拘束オートマトン(線形拘束された非決定性チューリングマシン)と等価である。これは、テープ長が kn セルに制限された非決定性チューリングマシンである。ここで n は入力の長さ、k はそのマシンに対応した定数である(つまりテープ長は入力の長さに比例する)。要するに、そのようなマシンで判定できる形式言語は文脈依存言語であり、文脈依存言語はそのようなマシンで判定できる。
このクラスの言語の集合は非決定性チューリングマシンの線形空間に受容されるのでNLIN-SPACE(Non-deterministic Linear Space)として知られている。同様に決定性チューリングマシンに受容される言語については LIN-SPACE と呼ぶ。LIN-SPACE は NLIN-SPACE の部分集合であることは明らかである。LIN-SPACE = NLIN-SPACE であるかどうかは不明であるが、一般に等価ではないと考えられている。