Übungen
Klicke auf eine Aufgabenüberschrift, um die Aufgabe zu öffnen!
PGM (Portable Graymap) kann als Sprache zur Beschreibung von Graustufenbildern aufgefasst werden. Das folgende Bild
wird wie folgt in der Sprache PGM beschrieben:
P2 4 2 7 0 1 2 3 4 5 6 7
(a) Welches Alphabet Σ liegt der Sprache PGM zu Grunde? Gib Beispiele für Wörter über Σ an, die zu PGM bzw. nicht zu PGM gehören.
(b) Verdeutliche am Beispiel PGM, was man unter Syntax und Semantik einer Sprache versteht.
Betrachte das Alphabet Σ = {0, 1}.
(a) Schreibe alle Wörter über Σ auf, die höchstens drei Symbole lang sind. Ordne sie nach ihrer Länge. Denke auch an das leere Wort.
(b) Welche deiner Wörter gehören zu Σ*, welche zu Σ+? Erkläre den Unterschied zwischen diesen beiden Mengen.
(c) Erläutere den Unterschied zwischen dem Wort 0 und dem leeren Wort ε.
(d) Ben behauptet: „Das Alphabet hat nur zwei Symbole. Deshalb gibt es auch nur endlich viele Wörter über diesem Alphabet.“ Nimm zu dieser Aussage Stellung und begründe deine Antwort.
Über dem Alphabet Σ = {a, b} sind folgende Sprachen gegeben. Das Zeichen ∅ bezeichnet die leere Menge.
L1 = ∅
L2 = {ε}
L3 = {a, ab, abb}
L4 = {a, ab, abb, abbb, ...} (Die Wörter von L4 bestehen aus genau einem a, gefolgt von beliebig vielen b, auch keinem.)
(a) Gib für jede Sprache an, ob sie endlich oder unendlich ist. Bestimme bei den endlichen Sprachen die Anzahl der Wörter.
(b) Erkläre, warum L1 und L2 unterschiedliche Sprachen sind. In welcher der vier Sprachen ist das leere Wort enthalten?
(c) Welche der vier Sprachen sind Teilmengen von Σ+? Begründe jeweils deine Entscheidung.
Trage deine Ergebnisse zu (a) bis (c) in die Tabelle ein. Gib bei einer unendlichen Sprache als Anzahl "unendlich" ein.
| Sprache | Endlich oder unendlich? | Anzahl der Wörter | Enthält ε? | Teilmenge von Σ+? |
|---|---|---|---|---|
| L1 | ||||
| L2 | ||||
| L3 | ||||
| L4 |
(d) Entscheide, ob die Menge {a, ab, c} ebenfalls eine Sprache über Σ ist. Begründe mithilfe der Definition einer formalen Sprache.
Ein Roboter verwendet das Alphabet Σ = {V, L, R}. Dabei steht V für einen Schritt vorwärts, L für eine Drehung nach links und R für eine Drehung nach rechts. Ein Programm wird als Wort über Σ aufgeschrieben.
(a) Die Sprache LStart soll genau die Wörter enthalten, die mit V beginnen. Gib drei Wörter aus LStart und drei Wörter aus Σ* an, die nicht zu LStart gehören. Entscheide auch, ob ε zu LStart gehört.
(b) Entwickle eine andere Sprache über Σ. Formuliere eine eindeutige Regel, die festlegt, welche Wörter dazugehören. Gib drei passende Wörter und drei Wörter über Σ an, die deine Regel nicht erfüllen.
(c) Tausche deine Regel mit einer Partnerin oder einem Partner. Lasst euch gegenseitig weitere Wörter zuordnen und prüft, ob eure Regeln eindeutig sind. Klärt insbesondere, ob das leere Wort erlaubt ist und ob eure Sprachen endlich oder unendlich sind.
(d) Nun soll V einen Schritt rückwärts bedeuten. Die Regeln für die erlaubten Symbolfolgen bleiben unverändert. Ändert sich dadurch die formale Sprache? Begründe und unterscheide dabei zwischen den Symbolfolgen und ihrer Bedeutung.