Lineárně ohraničený Turingův stroj
Pojem lineárně ohraničený Turingův stroj označuje v informatice Turingův stroj, který má omezení při zápisu na pásku. Na rozdíl od běžného Turingova stroje totiž nesmí zapisovat na neomezeně mnoho buněk pásky, ale pouze na prvních n buněk, kde n je omezeno lineární funkcí vzhledem k délce vstupního slova. V určitém smyslu je tak tento stroj bližší běžným počítačům.
Lineárně ohraničené Turingovy stroje umí akceptovat jazyky ze třídy kontextových jazyků. Lze dokázat, že pro každý lineárně ohraničený Turingův stroj lze sestrojit Turingův stroj, který nepotřebuje pásku delší než je délka vstupního slova.
 | Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |
| Teorie automatů: formální jazyky a formální gramatiky | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Každá úroveň jazyků je podmnožinou své nadřazené úrovně. – Každý automat a každá gramatika má svůj ekvivalent v nadřazené úrovni. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
