Formale Sprachen

 Unter Synatx versteht man allgemein ein Regelsystem zur Kombination elementarer Zeichen zu zusammengesetzten Zeichen in natürlichen oder künstlichen Zeichensystemen. Die Syntaxregeln der Grammatik der deutschen Sprache geben, z.B. an, in welcher Reihenfolge die Satzglieder (elementar) in einem Satz (zusammengesetzt) angeordnet werden dürfen.

Eine formale Sprache L über einem Alphabet ∑ ist eine Teilmenge aller möglichen Verknüpfungen des Alphabets.

Neben der Bezeichnung Nicht-Terminal (N) wird auch häufig der Begriff Variable (V) verwendet. Ebenso wird die Menge der Terminale auch mit ∑ angegeben, da die Terminale die Symbole des Alphabets der Sprache sind.

Die Grammatik der lal-Sprache wird formal wie folgt dargestellt:

Glal = (N, T, S, P)	Die Grammatik ist eine 4-Tupel
N = {S, A, B}	Die Nichtterminale sind Platzhalter für die Erzeugung von Worten. S steht als Platzhalter für die erste, A für die zweite und B für die dritte Silbe des Wortes der lal-Sprache.
T = {la, le, lu}	Die Terminale sind genau die Buchstaben bzw. Silben, die in den Wörtern der lal-Sprache vorkommen.
Startsymbol = S	Eines der Nichtterminale muss als Startsymbol definiert werden. Aus dem Startsymbol lassen sich alle Worte der Sprache ableiten.
P = {                   S -> laA|leA|luA,                   A->laB|leB|luB,                   B ->lu }	Die Produktionsvorschrift umfasst alle Ersetzungsregeln, die zur Erzeugung der Wörter der lal-Sprache nötig sind, z.B. kann das Startsymbol S durch laA oder luA ersetzt werden.

Formal  definiert man eine reguläre Grammatik als ein 4-Tupel G=(N, T, S, P)

-        N ist eine leere, endliche Menge, die Menge der nicht-terminale

-        S Element von N ist das Startsymbol

-        T ist eine nicht leere , endliche Menge, die Menge der Terminale

-        P ist die endliche Menge der Produktionen. Jede Produktion bildet eine beliebige Kombination aus Terminalen und Nicht-Terminalen, die mindestens ein Nicht-Terminal enthält, auf eine beliebige Kombination von Terminalen und Nicht-Terminalen ab.

Aufbau einer Produktionsvorschrift einer rechtsregulären Grammatik

N -> ϵ	ein Nicht-Terminal N kann durch das leere Wort ersetzt werden
N -> T	ein Nicht-Terminal N kann durch ein Terminal T ersetzt werden
N -> TN	ein Nicht-Terminal N kann durch ein Terminal und durch ein folgendes Nicht-Terminal ersetzt werden
N -> | TN	ein Nicht-Terminal kann durch eine der beiden Möglichkeiten ersetzt werden

Bei einer rechtsregulären Grammatik darf auf den linken Seiter ihrer Ersetzungsregeln jeweils nur ein Nicht-Terminal stehen. Das Nicht-Terminal darf nur durch das leere Wort, genau ein Terminal oder ein Terminal von einem Nicht-Terminal ersetzt werden.