Jahrgangsstufe Q2 - Informatik - Mittwoch, der 13. Januar 2021

Mein Name:
Jahrgang/Klasse:
Meine E-Mail-Adresse:

Automaten und Grammatiken

Lösungen vom 18. Dezember 2020


Aufgabe 1: Seite 17, (Abschnitt 2.4 Übungen), Aufgabe 5:

Antwort zu Aufgabenteil a):
Die folgenden Dualzahlen sind in der Grammatik ableitbar:
0, 11, 110, 1001, 1100 und 1111
Antwort zu Aufgabenteil b):
Die Ableitung von 10101 macht man so:
s_0 --> 1s_1 -->10s_2 --> 101s_2 --> 1010s_1 --> 10101s_0 --> 10101ε --> 10101


Aufgabe 2: Seite 18, (Abschnitt 2.4 Übungen), Aufgabe 7:

Die folgenden Wörter lassen sich in der Ipogesien-Grammatik ableiten:
ipigisi, isipisigisisisi

Aufgabe 3: Auf der Seite 27 ist in Abschnitt 3.2 beschrieben, wie man aus einem endlichen Automaten die zugehörige Grammatik systematisch entwickeln kann. Das Beispiel ist nachzuvollziehen und diese Vorgehensweise auf Aufgabe 2a auf Seite 28 (3.2.1 Übungen) zu übertragen.

Die Produktionen der Grammatik zum Automaten sehen wie folgt aus:
S --> 0S | 1A
A --> 1A | 0B
B --> 1C | 0S | 1
C --> 1A | 0B

Neue Aufgaben:



Seite 32, (Abschnitt 3.4 Vermischte Übungen), Aufgabe 2:

Zur Wiederholung: Die Definition eines endlichen Automaten findet man auf Seite 22 (Abschnitt 3.1.4).

Zu Aufgabenteil a): Ergänze!


Zur Wiederholung: Ein Beispiel einer Zustandstabelle eines endlichen Automaten findet man auf Seite 20 (Abschnitt 3.1.3).

Zu Aufgabenteil b): Ergänze!



Zu Aufgabenteil c): Es soll die Grammatik des abgebildeten Automaten entwickelt werden, und nicht, wie im Aufgabentext angegeben, eines Automaten für Wörter, die mit 007 enden.