Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.

====== Nicht-reguläre Sprachen ======
<WRAP center round info 80%>
Diejenigen Sprachen, die sich **mit endlichen Automaten beschreiben lassen**, heißen **reguläre Sprachen**. \\ \\ 
Ein Beispiel für eine Sprache, die **nicht regulär** ist, die die **Menge aller geklammerten Terme**. Sie lässt sich beispielsweise durch die Grammatik G = (V, A, P, S) beschreiben mit
  * der Menge der Nichtterminale V = { Buchstabe, Bezeichner, Operator, Term }
  * dem Alphabet A = {"a", ..., "z", "*", "/", "+", "-", "(", ")"}
  * dem Startsymbol S = Term
  * und den Produktionsregeln
<code>
R1: Buchstabe = "a" | "b" | ... | "z"
R2: Bezeichner = Buchstabe { Buchstabe }
R3: Operator = "+" | "-" | "*" | "/"
R4: Term = Bezeichner | Term Operator Term | "(" Term ")"
</code>
Die Regel R4 stellt sicher, dass der Term genausoviele öffnende wie schließende Klammern enthält und diese jeweils paarweise in der richtigen Reihenfolge einen Term umfassen. Dadurch sind Worte wie
  * ''5 + ) 3 + 4 (''
  * ''( (3 + 4) ) )''
  * ''2 + ( ( 4 - 7 )''
ausgeschlossen.
</WRAP>
<WRAP center round tip 80%>
**Warum gibt es keinen DEA, der die Sprache der geklammerten Terme beschreibt?** \\ \\ 
Versuchen Sie doch einfach, einen zu erstellen! So wird Ihnen am einfachsten bewusst, wo das Problem liegt. Am besten sehen Sie sich anschließend Abbildung 4 auf Seite 41 des Schulbuches "Informatik 7 (gA)" an und lesen den Text daneben.
</WRAP>

===== Weitere Beispiele nicht-regulärer Sprachen =====
  * alle Wörter über dem Alphabet A = {a, b}, die genausoviele a's wie b's enthalten.
  * die Programmiersprachen Java, C, Pascal usw. (wegen geklammerten Termen, Schachtelungsebenen von Scopes usw.)