Lernkarten
Welche 4 Typen von Grammatiken gibt es?
Typ 3: Reguläre Sprachen
Typ 2: Kontextfreie Sprachen, umfasst Typ 3
Typ 1: Kontextsensitive Sprachen. umfasst Typ 2
Typ 0: Phrasenstruktursprachen, umfasst Typ 1
Was ist ein Alphabet?
endliche, abgeschlossene Menge vereinbarter, eindeutiger, unterscheidbarer, unzerlegbarer Einzelzeichen / Symbole
Was ist eine Zeichenreihe?
Reihe aus Elementen eines Alphabets
Was ist eine Sprache?
Menge von Zeichenreihen aus Eingabezeichen
- Menge der Zeichenreihen einer natürlichen Sprache
- Menge aller von einem endlichen Automaten akzeptierten Zeichenreihen
Alphabete sind abgeschlossen gegenüber Mengenoperationen. Was bedeutet das?
Wenn zwei Alphabete durch eine Operation (z.B. Differenz, Vereinigung, Schnittmenge) verbunden werden, ist das Ergebnis ebenfalls ein Alphabet.
Bsp.: Wenn A und B reguläre Sprachen sind, dann ist auch A vereinigt B eine reguläre Sprache.
Für welchen Fall kann auf folgendem Wege die Anzahl der Elemente einer Vereinigungsmenge berechnet werden?
| Alphabet A vereinigt Alphabet B | = | Alphabet A | + | Alphabet B |
Diese Rechnung kann genutzt werden, wenn die Schnittmenge der beiden Alphabete die leere Menge ist, sie also keine gemeinsamen Elemente haben. Andernfalls würden diese doppelt gezählt werden.
Wie ergibt sich die Anzahl aller möglichen Teilmengen eines Alphabetes?
| Potenzmenge des Alphabetes | = 2 |Alphabet|
Wie wird die Konkatenation • einzelner Zeichen aus dem Alphabet \(\Sigma\) formal beschrieben?
\(\Sigma \times \Sigma \to \Sigma ^*\)
Das leere Wort \(\varepsilon\) ist das Neutralelement. Jedes Wort lässt sich als Verkettung beliebiger Zeichen aus \(\Sigma\) mit dem leeren Wort in beliebiger Häufigkeit darstellen. Z.B. w = ab = \(a\varepsilon\varepsilon b \varepsilon\)
