Formale Sprachen

Neben deiner Muttersprache kennst du sicher noch weitere Sprachen: Fremdsprachen (Englisch, Französisch, Spanisch …), Zahlen oder die Formelsprache der Mathematik. Auch in der Informatik gibt es Sprachen: Programmiersprachen (Python, Java, C, …) oder Auszeichnunssprachen (HTML, Latex, Markdown). Deshalb beschäftigt sich auch die Theoretische Informatik mit diesem Thema.

Alphabet

Ein Alphabet ist eine endliche, nicht leere Menge von Zeichen.

Beispiele:

Wort

Ein Wort über demAlphabet ist eine Zeichenkette, die ausschließlich aus Zeichen aus besteht. Das leere Wort ist ein Wort in jedem beliebigen Alphabet.

Die Länge eines Wortes kurz , ist bestimmt durch die Anzahl aller Zeichen, die das Wort enthält. Mehrfachvorkommen werden mehrfach gezählt. Für das leere Wort gilt

Formale Sprache

Die Menge aller Wörter über nennt man die Wortmenge . Sie ist abzählbar unendlich. Das leere Wort gehört zu jeder Wortmenge.

Eine (formale) Sprache ist eine beliebige Menge von Wörtern über .

Aufgabe 1

Arbeite auf der Seite https://flaci.com/ das Modul Formale Sprachen für jedes vorgegebene Alphabet einmal durch!

Aufgabe 2

Löse auf der Seite https://schuljahr.inf-schule.de/2019-20/sprachen/sprachenundautomaten/formalesprachen/uebungen die Aufgaben 2 und 3!