studyklar
GdI 1 · Übungsblatt 3 · Aufgabe 5

Wörter aus vier EBNFs erzeugen

Vier kurze Regeln in EBNF und sechs Wörter aus den Buchstaben a und b: Für jedes Paar ist zu prüfen, ob die Regel das Wort erzeugen kann. Rechts stehen die Regeln als Syntaxdiagramm und die Tabelle, die sich Spalte für Spalte füllt. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 3.5

Kreuzen Sie in der Tabelle an, welche der Worte mit den vorgegebenen EBNFs erzeugt werden können!

Wort \ EBNF{a} b [a]{a} | {b}{a | b}[a] {(ab)} [b] {a}
a b a
a a b
a a a
a a a b
b a
ε

Eine EBNF (erweiterte Backus-Naur-Form) ist eine Schreibweise für Regeln, die festlegen, welche Zeichenfolgen erlaubt sind. Ein Wort ist hier eine Folge der Buchstaben a und b; die Leerzeichen in „a b a“ dienen nur dem Lesen. ε ist das leere Wort, die Folge ohne einen einzigen Buchstaben.

„Eine EBNF erzeugt ein Wort“ heißt: Man kann die Regel so durchlaufen, dass genau dieses Wort herauskommt, kein Buchstabe mehr und keiner weniger. Angekreuzt wird jede Zelle, für die das geht. Die vier Regeln heißen hier der Reihe nach E1 bis E4.

Merke: „Ja“ zeigt man mit einem Weg durch die Regel. „Nein“ zeigt man mit einem Grund, warum es keinen Weg geben kann.
  1. Die Zeichen der EBNF klären: { }, [ ], ( ) und |.
  2. Spalte für Spalte jede Regel gegen alle sechs Wörter prüfen.
  3. Den schwierigsten Fall, a a a b bei E4, einzeln begründen.
Aus Skript 3, Folie 3-24 („Formale Sprachen“): Ein Wort über einem Alphabet ist eine Aneinanderreihung endlich vieler Symbole aus dem Alphabet; auch das „leere“ Wort ε zählt dazu.

Die Zeichen der EBNF

{ }: 0, 1, 2, … mal · [ ]: 0 oder 1 mal · ( ): Gruppe · |: oder

Die Buchstaben a und b sind Terminale: Sie stehen so im Wort, wie sie in der Regel stehen; in der EBNF sind sie nicht besonders gekennzeichnet. Alles andere sagt, wie oft und in welcher Reihenfolge sie vorkommen dürfen:

  • { x }: x darf beliebig oft hintereinander stehen, auch keinmal (n-fach, n ≥ 0).
  • [ x ]: x darf einmal stehen oder fehlen (optional).
  • ( x ): x ist eine Gruppe, die als Ganzes zählt. {(ab)} heißt: „ab“ beliebig oft, also ε, ab, abab, …
  • x | y: entweder x oder y (Alternative).
  • Was nebeneinander steht, kommt im Wort in dieser Reihenfolge.

Im Syntaxdiagramm rechts wird daraus ein Weg von links nach rechts: { } ist eine Schleife zurück, [ ] ein Umweg, | eine Weiche.

Skript · EBNF (Skript 3, Folie 3-33)
Klammern: ( ) Inhalt ist gruppiert; [ ] Inhalt ist optional; { } Inhalt kann n-fach stehen, n ≥ 0. Alternativen werden durch | dargestellt. Terminale nicht speziell gekennzeichnet.

E1 = {a} b [a]

WortE1Weg durch {a} b [a]
a b aja{a} = a, b, [a] = a
a a bja{a} = a a, b, [a] leer
a a aneinkein b; E1 braucht genau ein b
a a a bja{a} = a a a, b, [a] leer
b aja{a} keinmal, b, [a] = a
εneinkein b

E1 hat drei Teile in fester Reihenfolge: beliebig viele a, dann genau ein b, dann höchstens ein a. Jedes Wort von E1 enthält also genau ein b, und hinter dem b steht höchstens ein a. Damit fallen a a a und ε weg: Ihnen fehlt das b. Bei den anderen vier Wörtern zeigt die Tabelle, wie oft {a} läuft und ob [a] genutzt wird.

Noch 5 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Abbildung 1

E1abaE2abE3abE4aabba
LegendeOval: Buchstabe (Terminal). Schleife zurück: { }. Umweg darüber: [ ].

Abbildung 1

WortE1{a} b [a]E2{a} | {b}E3{a | b}E4[a] {(ab)} [b] {a}
a b a????
a a b????
a a a????
a a a b????
b a????
ε????
Legende▸ gerade geprüftDie ausgefüllte Tabelle: ✓ ja = erzeugbar, – nein = nicht erzeugbar.