| Infos Home | Impressum | Original Artikel & Autoren Liste |
Eine LBA kann ein um einen konstanten Faktor größeres Band simulieren, indem das Bandalphabet -Tupel des Eingabealphabetes enthält. Entsprechend wäre auch eine Definition denkbar, bei der gleich ein um einen konstanten Faktor größeres Band vorgesehen wird. Die nutzbare Bandlänge ist dann linear in der Länge der Eingabe. Dies erklärt den Namen der LBA.
Die von nichtdeterministischen LBAs akzeptierten Sprachen sind genau die kontextsensitiven Sprachen (vgl. Chomsky-Hierarchie).
Es ist ein offenes Problem, ob deterministische LBAs die gleiche Sprachklasse akzeptieren wie die nichtdeterministischen.
|
Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste"). Der Text steht unter der GNU Freie Dokumentation Lizenz. |