Zur Themenübersicht     

Will ich Sprachen klassifizieren gibt es dazu grundsätzlich zwei Möglichkeiten:

1. Analysierende Methode:

Ich prüfe, ob mir vorliegende Worte zu einer Sprache gehören. Informatisch gedacht heißt dies, ich benötige einen Algorithmus oder einen Automaten oder irgendeine anderes Objekt, welches in der Lage ist, nach Eingabe eines Wortes festzustellen, ob dieses zu der Sprache gehört oder nicht.
So können wir zu jedem erkennenden Automaten eindeutig eine Sprache über dem Eingabealphabet dieser Sprache definieren:

Ein Problem tut sich hier auf: ich kann so nur schon vorhandene Worte (oder Sätze) daraufhin prüfen, ob sie zu einer Sprache gehören. Zum Sprechen gehört aber auch, dass man in der Lage ist, Worte (bzw Sätze) zu erzeugen. !!!

2. Erzeugende Methode:

Ich benötige irgendein System, welches mir auf irgendeine Weise Worte dieser Sprache erzeugt. Hierzu gehören unter anderem die (formalen) Grammatiken. Wir werden aber noch andere solche Systeme kennen lernen. Genannt seien Syntaxdiagramme und die Sprachdefinition nach Backus-Nauer.

Im Folgenden beschäftigen wir uns mit der Klassifizierung von Sprachen nach dem erzeugenden System einer Grammatik.

Nach Chomsky werden die Grammatiken je nachdem welchen Einschränkungen die zugehörigen Ersetzungsregeln  unterliegen, in verschiedene Klassen unterteilt. Analog werden die zugehörigen Sprachen ebenso klassifitiert.

Sei G eine Grammatik, N die Menge der Nichtterminalsymbole, T die Menge der Terminalsymbole und l das leere Terminalsymbol.
Eine Grammatik heißt:

• Chomsky-Typ-3-Grammatik oder (rechts)lineare Grammatik, falls alle Ersetzungsregeln von der Form
  

  A -> l 
  A -> a
  A -->aB

  sind, wobei a Î T und A,B Î N;
   
  
• Chomsky-Typ-2-Grammatik oder kontextfreie Grammatik, falls alle Ersetzungsregeln von der Form
  

  A -> y

  sind, wobei y eine beliebige endliche Folge von Terminalen und Nichtterminalen ist.
   
  

• Chomsky-Typ-1-Grammatik oder kontextsensitive Grammatik, falls alle Ersetzungsregeln von der Form
  

  j₁Aj₂ -> j₁yj₂

  sind, wobei j₁, j₂, y   beliebige endliche Folgen von Terminalen und Nichtterminalen sind und y ¹ l ist.
   
  
• Chomsky-Typ-0-Grammatik oder allgemeine Grammatik, falls die Ersetzungsregeln in keiner Weise eingeschränkt sind.

Anmerkungen:

• Die Bezeichnung rechtsslinear stammt daher, dass in den Ersetzungsregeln stets nur ein Terminal und ein Nichtterminal vorkommen dürfen, wobei das Nichtterminalsymbol immer rechts vom Terminalsymbol steht. Dies führt dazu, dass bei Ableitungsbäumen der entstandene Ausdruck immer nach rechts ergänzt wird.
• Bei kontextsensitiven Grammatiken, hängt es von den vor und hinter einem Terminalsymbol stehenden Zeichen ab, wie das  Nichtterminalsymbol zu ersetzen ist. Es kommt also auf den Zusammenhang , den Kontext eines Zeichens an.
• Der Begriff kontextfrei ergibt sich dann von selbst.

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite