Übungen
Tor oder kein Tor?
Auf dieser Seite lernst du einen Akzeptor kennen, der Torjubel erkennt. Der reguläre Ausdruck to+r und das dazu passende Syntaxdiagramm sollen dabei die formale Sprache der Torjubel definieren. Beispiele für Wörter dieser Sprache wären tor, tooor oder tooooooor. Dagegen sind nach dieser Definiton trr, tooro oder ttooor keine Torjubel.
In der Simulation siehst du den Akzeptor für diese Sprache. Das Zustandsdiagramm des Akzeptors besitzt fünf Zustände (Z0 bis Z4) und Pfeile für die Zustandsübergänge, an denen Eingabezeichen stehen.
Aufgabe 1 - Torjubel
Teste den Akzeptor, in dem du in der Simulation unten einen Torjubel eingibst und anschließend auf den Pfeil klickst. Nun kannst du die Abarbeitung des Eingabeworts schrittweise ausführen.
Beobachte die Ausführung bei verschiedenen Eingabewörtern (toor, tro, torr...) und beantworte dabei die folgenden Fragen:
- Wo sehe ich, welche Eingabezeichen erlaubt sind?
- Woran erkenne ich den Zustand, in dem der Akzeptor beginnt?
- Was passiert in einem Arbeitsschritt des Automaten?
- Wie lange arbeitet der Akzeptor?
- Wann und wie entscheidet der Automat, ob eine Eingabe akzeptiert wird?
Jetzt hast du erste Erfahrungen mit Akzeptoren gemacht und kannst in der nächsten Aufgabe einen Automaten in der Simulation teilweise selbst definieren. Du kannst dabei deinen Automaten am Ende in der Simulation lokal speichern oder mit dem Teilen-Symbol durch einen Code für alle zugänglich machen.
Aufgabe 2 - Lachlaute
In der Simulation siehst du einen Akzeptor, der die formale Sprache der Lachlaute erkennen soll. Lachlaute sind z.B.
ha oder hahaha und werden mit dem regulären Ausdruck (ha)+ definiert. Im Syntaxdiagramm siehst du zum Vergleich ebenfalls die Bildungsregeln für Lachlaute.
Der Akzeptor ist allerdings noch nicht komplett konstruiert. Das soll gleich deine Aufgabe sein!
- Teste den Akzeptor mit den Wörtern
haundaha. - Teste nun mit
hh, analysiere die Fehlermeldung und ergänze dann den fehlenden Übergang im Zustand Z1 (Schaltfläche: Pfeil mit Pluszeichen). - Ergänze den passenden Übergang, damit das Wort
hahaakzeptiert wird. Überlege dir dabei genau, in welchen Zustand der Akzeptor wechseln muss, wenn im Zustand Z2 ein "h" eingelesen wird. Teste anschließend auch mit den Eingabenhahahaundhahah. - Kontrolliere mithilfe der Schaltfläche "Prüfen" (Pfeil mit Fragezeichen) ob es noch weitere fehlende Zustandsübergänge gibt und ergänze sie gegebenenfalls.
Aufgabe 3 - Ich denke nach ...
Die formale Sprache des lauten Nachdenkens soll alle Wörter vom kurzen Überlegen ("hm") bis zum Nachdenken ohne Ende ("hmmmmmmmmm" usw.) enthalten. Schaue dir das Syntaxdiagramm genau an und
formuliere dann hier zunächst den dazu passenden regulären Audruck.
Regulärer Ausdruck für Nachdenken:
Klicke auf einen Schalter, um die Aufgabe zu öffnen!
Welche Sprachen werden durch die abgebildeten Zustandsgraphen definiert? Beschreibe umgangssprachlich und gib den passenden regulären Ausdruck ein!
Zeichne zu allen Sprachen das passende Syntaxdiagramm!
| Nr. | Zustandsgraph | regulärer Ausdruck |
|---|---|---|
| A |  |
|
| B |  |
|
| C |  |
|
| D |  |
Erstelle einen Akzeptor, der Muh-Laute gemäß dem folgenden Syntaxdiagramm erkennt.
Formuliere hier zunächst den passenden regulären Ausdruck und teste
deinen Akzeptor am Schluß mit den aufgeführten Beispielen.
Erstelle einen Akzeptor, der Wörter erkennt, in denen die Bitfolge 001 vorkommt.
Formuliere hier zunächst den zum Syntaxdiagramm passenden regulären Ausdruck und teste
deinen Akzeptor am Schluß mit den aufgeführten Beispielen.
Erstelle Akzeptoren für die A-B-Sprache, die wie folgt arbeiten:
- Nichts wird akzeptiert.
- Nur das leere Wort (Länge 0) wird akzeptiert.
- Alle Wörter werden akzeptiert.
Die folgende Automatentafel gehört zu einem Akzeptor mit Z = {Z0, Z1, Z2, Z3, Z4} und Ze = {Z3}. Erstelle in der Simulation den Akzeptor, teste ihn und gib im Anschluß die Sprache des Akzeptors als regulären Ausdruck an!
Regulärer Ausdruck:
Bei der Datenübertragung werden häufig Prüfbits eingesetzt. Ein einfaches Verfahren hierbei ist das Paritätsbit. Bei diesem Verfahren wird nach einer bestimmten Zahl von Datenbits ein Bit angehängt, um z.B. die Anzahl der Einsen gerade zu machen.
In dieser Aufgabe soll nach drei Datenbits immer viertes Bit als Prüfbit angehängt sein. An die Bitfolge "001" (ungerade Anzahl 1er) würde eine "1" angehängt und an die Bitfolge "110" (gerade Anzahl 1-er) eine "0".
Beispiele: 0000, 1100, 11110011, 101000111001.
Gegenbeispiele: 1110, 0001, 111100001110, 110.
Erstelle einen Akzeptor, der eine Bitfolge einliest und nur dann akzeptiert, wenn alle Prüfbits korrekt sind (und die Folge mit einem Prüfbit endet).
Erstelle einen Akzeptor für E-Mail-Adressen. Die Adressen sollen nach folgendem regulären Ausdruck aufgebaut sein:
b+(.b+)*@b+.bbb?