Ü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 L1 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 L1 nicht regulär ist?
Zeige, dass die Sprache L1 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 L2 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 L3 der mathematisch korrekten ipigisi-Folgen
ebenfalls regulär?
Was meinst du? Wie müsste man argumentieren?