Wörter
Wörter sind eine Folge von Buchstaben. In der Fachsprache der Informatik entspricht ein Wort einer beliebigen Aneinandereihung von Buchstaben, im Gegensatz zu natürlichen Sprachen, in denen nur bestimmte Buchstabenfolgen sinnvolle Wörter ergeben.
Formal definieren wir Wörter wie folgt:
- Sei \( \sum \) ein Alphabet. Ein Wort über \( \sum \) ist eine endliche (eventuell leere) Folge von Buchstaben aus \( \sum \).
- Das leere Wort \( \epsilon \) ist die leere Buchstabenfolge.
- \( \sum^* \) ist die Menge aller Wörter über \( \sum \).
Sprachen
Und was sind nun Sprachen? Unter dem Begriff Sprache verstehen wir nun eine Menge von Wörtern über einem festen Alphabet:
- Eine Sprache \( \mathcal{L} \) über einem Alphabet \( \sum \) ist eine Teilmenge von \( \sum^* \).
- \( \mathcal{L}_\emptyset = \emptyset \) ist die leere Sprache.
- \( \mathcal{L}_\epsilon = \{\epsilon\} \) ist die einelementige Sprache, die nur aus dem leeren Wort besteht.