Übungen
Klicke auf einen Schalter, 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.
Emoticons werden oft in SMS und E-Mails benutzt, um emotionale Zustände zu beschreiben.
hi morgen könnte es endlich klappen :-) bin aber trotzdem noch etwas :< es is halt wie es is ;-) bye
Hier eine Übersicht mit häufig benutzten Emoticons (vgl. Wikipedia):
| Zeichenfolgen | Bedeutung |
|---|---|
:-) :) =) :] :> :c) x) :o) |
lächeln, Freude |
:-( :( =( :[ :< :/ x( :o( :C |
|
:'( :'C |
|
;-) ;) ;] ;o) |
|
:-P :b :p =P :P xP ;-P :oP |
|
:-D ;D :D =D xD XD :oD |
|
:-0 :-o :o =O :0 =o |
(a) Ergänze die Bedeutung der Zeichenfolgen in der Tabelle.
(b) Welche "Bausteine" werden zur Konstruktion von Emoticons benutzt? Gib ein Alphabet zur Sprache der Emoticons an.
(c) Gib Beispiele für Zeichenfolgen an, die aus den in (b) aufgelisteten Bausteinen bestehen und - nach derzeitigem Stand - wohl nicht zur Sprache der Emoticons gehören.
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) 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.
(d) Erläutere den Unterschied zwischen dem Wort 0 und dem leeren Wort ε. Ist ε hier ein Symbol des Alphabets?
Ü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.
(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.