Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-3-4

Beantwortet: Pumping-Lemma

Mon, 10 Jan 2022 21:33:53 +0000

Hallo uqyws,

zu 1) eine Sprache ist regulär, wenn man alle Wörter durch Vereinigung, Produkt und Iteration über die Basismenge schreiben kann. Das Produkt ist (soweit ich weiß) nur für zwei Elemente bzw. Sprachen definiert, also m^n geht zum Beispiel nicht, daher gibt es nicht die Möglichkeit bei L1 gleich viele b's und c's zu garantieren. L2 wird einfach als b^*c^* definiert, m und n sind unabhängig (m,n>=0 nach Definition, wäre es >=1 müsste man bb^*cc^* schreiben, damit garantiert man mindestens ein b und ein c) und ist damit regulär.

Zu 2.) Die Schleife ist direkt am Anfang und ist nur ein Zeichen lang, dann wird entweder ein a gepumpt und das Wort gehört immer noch zu L1 (die a's sind unabhängig von den b's und c's) oder es wird ein b oder c gepumpt (d.h. es ist kein a darin, das wäre am Anfang), dann gehört das Wort zu L2. Das heißt, die Bedingungen vom PPL werden erfüllt, das war die Aufgabe.
Bei AU-1-3 ist bei L6 zum Beispiel die Anzahl der 1en abhängig von der Anzahl der 0en (doppelt so viele), daher funktioniert das dort nicht. Hier ist entweder die Anzahl der a's egal (wenn ein a vorhanden ist L1) oder das Wort gehört zu L2 und dann ist die Anzahl der b's oder c's egal.

Falls noch etwas unklar ist, frage einfach noch einmal.

Viele Grüße

Anne (Tutorin)

Beantwortet: (2) Eliminiere reine Umbenennungen

Thu, 02 Feb 2017 14:49:49 +0000

Hi,

da habe ich vorhin nicht genau hingeguckt.

Leider ist die von Ihnen angegebene Regelmenge doch nicht äquivalent, da Sie A ja vollständig abschaffen.
Das führt aber zu Problemen, denn:

Durch Ihre Regelmenge P' kann man das Wort ax + xa erzeugen.
(S -> aSa ->aS+Sa ->ax+SA->ax+ax)

Diese Worte sind jedoch nicht in der Sprache enthalten, die durch die Grammatik mit P erzeugt wird.

Beantwortet: Monotone und kontextsensitive Grammatiken AU-3-4

Sun, 08 Jan 2017 14:27:30 +0000

$S' \rightarrow ZB$ ist kontextsensitiv, da nur ein Nonterminalsymbol ($S'$) auf eine nicht-leere Menge an Terminal- und/oder Nonterminalsymbolen abgeleitet wird und da der Kontext beibehalten wird. Der Kontext vor und nach $S'$ ist hier lambda.

$S' \rightarrow ZB$ ist monoton,da $|S'| \leq |ZB| \rightarrow 1 \leq 2$.

Alle kontextsensitiven Grammatiken sind auch monoton. Nicht alle monotenen Grammatiken sind kontextsensitiv. Man kann aber zu jeder monoten Grammatik eine kontextsensitive Grammatik finden, die die gleiche Sprache definiert. Monotone und kontextsensitive Grammatiken sind also gleich "mächtig" und charakterisieren deshalb die gleiche Sprachklasse (Typ-1-Sprachen).

Die rechtslinearen Grammatiken sind eine Teilmenge der regulären Grammatiken. Es gibt z.B. noch linkslineare Grammatiken, die auch zu den regulären Grammatiken gehören.
Die rechstlinearen Grammatiken sind aber genau so "mächtig" wie die regulären Grammatiken, sie charakterisieren also die gleiche Sprachklasse (Typ-3-Sprachen).

Viele Grüße

Philipp (Tutor)

Beantwortet: BX-> BAX

Sun, 07 Feb 2016 12:16:19 +0000

Weil je nach Sichtweise entweder $B$ im Kontext von $X$ durch $BA$ ersetzt wird (vorderer Teil des Kontexts ist in idesem Fall leer) oder $X$ im Kontext von $B$ durch $AX$ (hinterer Teil in diesem Fall leer).

Viele Grüße

Lukas König

Beantwortet: b): Warum ist S -> λ nicht kontextsensitiv ?

Tue, 22 Sep 2015 07:07:19 +0000

Hallo,

zunächst einmal, die Aufgabe war eine Klausuraufgabe, und wir haben damals Ihren Lösungsvorschlag auch gelten lassen.

Es ist so, dass eine kontextsensitive bzw. monotone GRAMMATIK die Regel $ S \rightarrow \lambda $ enthalten darf, wenn S auf keiner rechten Seite vorkommt. Das ist aber eine Ausnahme, die eingeführt wird, damit man das leere Wort mit Typ1-Grammatiken bilden kann. $ S \rightarrow \lambda $ für sich alleine gesehen ist sicher keine kontextsensitive bzw. monotone REGEL, da die wichtige Eigenschaft solcher Regeln ist, dass sie nicht zu einer verkürzenden Ableitung führen dürfen ($ S \rightarrow \lambda $ bedeutet, dass wir das Symbol S verschwinden lassen, also das abgeleitet Wort um ein Zeichen verkürzen).

Wir wollten hier darauf hinaus, dass Sie die Regeln einzeln betrachten, nicht die Grammatik ansich, daher auch der Zusatz: "Betrachten Sie die einzelnen Regeln hierbei unabhängig voneinander."

Aber alles in allem ist es uns am allerliebsten, wenn Sie den Stoff soweit verstanden haben, dass Sie unsere Lösung konstruktiv infrage Stellen können. Wie gesagt, falsch wäre Ihre Lösung auch nicht gewesen.

Viele Grüße

Lukas König

Beantwortet: Beispiel zur Zusammenfassung von Regeln

Tue, 22 Sep 2015 07:03:00 +0000

Bei deinem zweiten Beispiel hat man nach dem Ersetzen

$ S \rightarrow aAb|ab $

$ A \rightarrow aAb|ab $

man sieht, das man aus S und A genau das gleiche ableiten kann, daher kann man A und S zu einem Nonterminalsymbol zusammenfassen (hier zu S) und die Grammatik dadurch vereinfachen:

$ S \rightarrow aSb|ab $

Ich persönlich glaube nicht, in der Klausur Punkte abgezogen würden, wenn man diese Vereinfachung nicht macht (das ist keine verbindliche Aussage).

Bei der Aufgabe AU-3-4 unterscheiden die Produktionen sich:

aus S kann man zusätzlich A-S ableiten, daher kann A und S nicht zu einem Nonterminal zusammenfassen.

Kurz gesagt, wenn du dir nicht sicher bist, dann mach nur die Ersetzung und keine Vereinfachungen. Die Vereinfachung ist soweit ich sehe nicht notwendig, um auf eine CNF zu kommen.

Gruß,

Tobias (Tutor)

Beantwortet: Zusammenfassen der Regeln möglich?

Tue, 22 Sep 2015 06:59:37 +0000

Zunächst: ich kann nicht nachvollziehen, wie du auf $x|aSa|bSb$ kommst. Ersetzen von $S\rightarrow A$ mit den Produktionen, bei denen $A$ links steht, führt auf $ S\rightarrow x|aAa|bAb$ . Was hast du noch gemacht?

Kannst du eine Aufgabe nennen, in der die Zeile gelöscht wird? Ohne eine solche Aufgabe gesehen zu haben, vermute ich, dass dort das Zeichen, das in der gelöschten Produktion links stand, auf keiner rechten Seite mehr vorkam und die betroffene Produktion daher überflüssig geworden ist.

Bei dieser Aufgabe darfst du $A \rightarrow $ ... nicht löschen, da du sonst das $A$, das z.B. bei der Anwendung von $S\rightarrow S-A$ entsteht, nicht in Terminalsymbole umwandelnt kannst!

Gruß,

Tobias (Tutor)

Beantwortet: Wie wird eine Grammatik λ- frei?

Tue, 22 Sep 2015 06:54:18 +0000

Hallo,

in den Vorlesungsunterlagen gibt es dazu eine etwas technische Beschreibung (VL 3 Folie 14).

Ich habe versucht das verbal noch ein wenig zu umschreiben, aber am besten schaust du dir das jeweils in Verbindung mit dem Algorithmus an.

Im grunde steht dort:

- zuerst ermittle alle Nonterminalsymbole, die auf λ abbilden und sammle diese in einer Menge U

- dann suchst du iterativ nach Nonterminalsymbole, die auf die Nonterminalsymbole aus deiner Menge U abbilden und nimmst sie ebenfalls in U auf. (Tu das bis U sich nicht mehr ändert)

-jetzt ist die Menge U also mit lauter Nonterminalsymbolen voll, die in beliebig vielen Schritten auf λ abbilden

Nun konstruiertst du deine neue Grammatik:

-ausgehend von der ursprünglichen Abbildungsregelmenge P fügst du für alle Regeln mit einem Symbol aus U auf der rechten Seite die gleiche Regel ohne jenes Symbol aus U ein (du lässt also nur den Kontext stehen- so sparst du dir den weg über viele umformungen und könntest das gleich mit λ ersetzen)

-schließlich löscht du alle Regeln die direkt auf λ verweisen

liebe Grüße

Bastian (Tutor)