Übungen

Aufgabe 1 - ipigisi

Die ipigisi-Sprache wird im Abschnitt Fachkonzept - Formale Sprachen erläutert.

(a) Eine isi-Folge ist eine Folge von i-Symbolen, bei der jeweils benachbarte i-Symbole durch ein s getrennt sind: i, isi, isisi, ....

Für die Sprache L₁ der isi-Folgen kann man folgende Grammatik entwickeln:

F -> I
F -> iSi
S -> sIs
I -> iSi
I -> i
S -> s

Warum kann man jetzt nicht erschließen, dass die Sprache L₁ nicht regulär ist? Zeige, dass die Sprache L₁ der isi-Folgen regulär ist.

(b) Eine ipigisi-Folge hat die Struktur isi-Folge p isi-Folge g isi-Folge. Beispiele für solche ipigisi-Folgen sind: ipigi, ipigisi, isipigisi, isipigisi, ....

Auch die Sprache L₂ der ipigisi-Folgen ist regulär. Welche Nachweisverfahren gibt es, um das zu zeigen? Wähle eines der Nachweisverfahren aus und führe den Nachweis.

(c) Ein mathematisch korrekter ipigisi-Ausdruck ist eine ipigisi-Folge, bei der die Summe der i-Symbole vor und nach dem g-Symbol gleich sind.

Ist die Sprache L₃ der mathematisch korrekten ipigisi-Folgen ebenfalls regulär? Was meinst du? Wie müsste man argumentieren?