Siehe auch

• Lindenmayer-Systeme
  
• Chomsky-Hierarchie
  
• Formale Grammatik
  

Anwendungen siehe in:
.

• Berechenbarkeitstheorie
  
• Komplexitätstheorie
  
• Kryptographie
  
• Kryptanalyse
  
• Compilerbau
• Programmiersprache
• H. Göttler: Mündliche Prüfung TGI[1]

weitere Sprechweisen

Ein Wort einer formalen Sprache heißt häufig auch String oder Zeichenkette. Das leere Wort heißt in der Algebra auch neutrales Element.

Operationen auf formalen sprachen

Also alle Wörter, die man bilden kann, indem ein Wort aus und ein Wort aus aneinandergereiht werden.Die Konkatenation zweier sprachen und ist .

Man kann durch induktiv die Potenz einer Sprache für mit definieren, dabei wird und definiert (beachte: die Menge, die nur das leere Wort enthält, ist selbst nicht leer!).

Jetzt können wir die Menge aller endlichen Wörter über dem Alphabet hinschreiben: , wobei und wir hier die Symbole aus mit den Wörtern der Länge 1 identifizieren.

Die Operation wird auch als endlicher (oder kleenescher) Abschluss bezeichnet, der Operator selbst als Kleene-Stern (siehe Kleenesche Hülle).

unendlichen Sprache.Die Menge dieser Wörter kann endlich oder unendlich sein. Man spricht dann auch von einer endlichen bzw.