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 $A$ ist eine endliche, nicht leere Menge von Zeichen.

Beispiele:

$A = \{0, 1\}$
$A = \{A, B ... Z, a, b, ..., z\}$
$A = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

Wort

Ein Wort $w$ über demAlphabet $A$ ist eine Zeichenkette, die ausschließlich aus Zeichen aus $A$ besteht. Das leere Wort $\varepsilon=""$ ist ein Wort in jedem beliebigen Alphabet.

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

$$|\varepsilon|=0$$

Formale Sprache

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

Eine (formale) Sprache $L \subseteq A^*$ ist eine beliebige Menge von Wörtern über $A$.

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!