Lineare Sprache

Die Linearen Sprachen (englisch linear languages, LIN) sind ein Fachbegriff aus der Theoretischen Informatik. So sind sie hier speziell eine Klasse formaler Sprachen und stellen dabei eine echte Teilklasse der Typ-2-Sprachen der Chomsky-Hierarchie dar. Gleichzeitig enthalten sie die regulären Sprachen als echte Teilmenge.

Die Bedeutung der linearen Sprachen liegt in der Hauptsache darin, dass sie ein Beispiel für eine einfach zu verstehende Klasse formaler Sprachen darstellen.

Eine formale Sprache ist genau dann linear, wenn eine lineare Grammatik existiert, die diese Sprache erzeugt. Eine kontextfreie Grammatik heißt lineare Grammatik, wenn auf der rechten Seite einer jeden Regel maximal ein Nichtterminal vorkommt. In der Fachliteratur hat sich die Abkürzung LIN durchgesetzt.

Lineare Grammatik ist ein Begriff aus der Theorie der formalen Sprachen in der theoretischen Informatik. Eine lineare Grammatik ist ein Spezialfall einer kontextfreien Grammatik. Bei ihr gilt gegenüber der kontextfreien Grammatik die zusätzliche Einschränkung, dass auf der rechten Seite jeder Produktionsregel höchstens ein Nichtterminal stehen darf.