Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in SPR-AE

Kommentiert: Die Menge der konextfreien Sprachen ist gegenüber der Komplementbildung abgeschlossen.

Wed, 15 Jun 2016 19:14:01 +0000

...und diese Aufgabe ist tatsächlich nicht einfach! Wenn Sie die komplett verstanden haben (also alle Heimaufgaben vom 3. Blatt), dann sind Sie schon recht gut vorbereitet...

Antwort bearbeitet: DEA und NEA für $\emptyset$, $\lambda$ und $E^\star$

Mon, 09 Feb 2015 18:53:03 +0000

Der NEA für die leere Menge $L=\emptyset$ sieht folgendermaßen aus:

Script:

fsm:

s0;

Der NEA für $L=E^\star$ sieht so aus (unabhängig vom Inhalt von $E$):

Script:

fsm:

s0:f;

Der entsprechende DEA für die leere Menge ergibt sich (abhängig von $E$) aus dem NEA durch den Algorithmus aus der Vorlesung zu ($E$ soll dabei für alle Zeichen $e \in E$ stehen):

Und der DEA für $E^\star$ analog zu:

Ein NEA für die Sprache $L=\{\lambda\}$ ist:

Script:

fsm:

s0:f-E-s1;

Und der entsprechende DEA:

Warum das so ist, lasse ich Sie erst einmal selber überlegen, aber Sie dürfen gerne nochmal nachfragen, wenn es weitere Unklarheiten gibt.

(Selbstverständlich sind alle DEAs auch NEAs, aber nicht umgekehrt. NEAs kann man sich also in gewisser Weise schenken, wenn DEAs gegeben sind - aber natürlich sind die NEAs hier kompakter als die zugehörigen DEAs. Die angegebenen DEAs hier sind alle minimal, bei den NEAs haben wir keinen Minimalitäts-Begriff definiert.)

Antwort bearbeitet: Wieso kann eine Teilmenge, die nicht regulär ist, Teil einer regulären Sprache sein?

Wed, 14 Jan 2015 13:26:29 +0000

Ganz einfach: Nehmen Sie doch mal die Sprache $E^\star$ für irgendein Alphabet $E$. Diese Sprache ist definitiv regulär, denn ein endlicher Automat muss einfach nur alle Wörter akzeptieren (wie der Automat aussieht, können Sie sich ja mal überlegen). Wenn es stimmen würde, dass alle Teilmengen von regulären Mengen wieder regulär sind, dann gäbe es ja gar keine nicht-reguläre Sprachen.

Salopp gesagt entsteht die Schwierigkeit von Sprachen dadurch, dass man sich von den beiden trivialen Sprachen $\emptyset$ und $E^\star$, bzw. noch allgemeiner, von Regelmäßigkeiten ("Mustern") in der Wortbildung entfernt. Da kann man tun, indem man Wörter hinzufügt, aber auch, indem man Wörter weglässt. Hat man etwa die Sprache

$$\{a^nb^n \ | n \in \mathbb{N}\}$$

dann könnte man die Sprache schwieriger machen, indem man bspw. noch alle Wörter hinzunimmt, deren Länge eine Primzahl ist (unabhängig von $n$). Man könnte sie aber auch schwieriger machen, indem man alle Wörter entfernt, für die $n$ eine Primzahl ist.

PS. Diese Analogie stimmt nicht:

Grammatiken eines Typs i können nur von Sprachen eines Typs j mit j >= i erzeugt werden. Dann müsste ja meiner Überlegung nach eine reguläre Sprache nur reguläre Sprachen enthalten dürfen richtig?

Eine reguläre Sprache ist etwas anderes als die Menge aller regulären Sprachen.

Beantwortet: Wieso ist E* regulär?

Sun, 16 Nov 2014 16:24:51 +0000

Wie du angemerkt hast, bedeutet E* alle möglichen Kombinationen von Zeichen aus dem Alphabet E. Das heißt, um zu entscheiden, ob ein Wort in E* liegt, muss man nur nachschauen, ob alle Zeichen des Wortes in E enthalten sind. Es ist also nicht nötig, beim von dir angeführten $a^n b^n c^n$ zu prüfen, ob die Anzahl der a, b und c gleich ist (was ein endlicher Automat nicht kann).

Tobias (Tutor)

Beantwortet: E* regulär oder nicht?

Sun, 16 Nov 2014 16:22:47 +0000

Hallo,

es gilt, dass sowohl die leere Menge als auch E* reguläre Sprachen sind.

Das bleibt auch in Teil 2 erhalten. "B c E* nicht regulär" muss man verstehen als "B, welches eine Teilmenge von E* bildet, ist nicht regulär". Über E* selbst wird hier keine Aussage getroffen.

Viele Grüße

Philippe (Tutor)