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

Wieso ist das PPL erfüllt?

Fri, 05 Jan 2018 12:44:07 +0000

Bsp x=lambda y=ab und z= c mit i=2 wäre das Wort nicht in L1 enthalten.

w=xy²z = (ab)²c = ababc nicht Element der Sprache

1) |xy| <= 3 2) |y|>=1 3) für alle i erfüllt =>alles erfüllt

Bei dem PPL muss ja jede mögliche Zerlegung xyz möglich sein.

Beantwortet: Erklärung PPL (2)

Fri, 27 Jan 2017 12:33:01 +0000

Ich bin nicht sicher, was Sie hier versuchen, denn Sie beziehen sich ja nur auf einen Teil der Sprache $L_1$. Wichtig ist zu verstehen, dass wir hier ausnahmsweise andersherum vorgehen als sonst - wir wollen diesmal wirklich eine Zerlegung finden, sodass die Eigenschaften (1), (2) und (3) gelten. Und nicht - wie normalerweise - zeigen, dass es keine Zerlegung gibt, für die diese Eigenschaften gelten.

In Ihrer Argumentation schreiben Sie, $xy$ könne nur zwei der drei Buchstaben enthalten - dabei sind Sie aber auf der klassischen Schiene mit dem Widerspruchsbeweis. Stattdessen können wir es uns diesmal leicht machen und tatsächlich eine Zerlegung auswählen. Es reicht uns, eine zu finden, wir müssen nicht über alle argumentieren.

Und diese eine legen wir einfach fest durch

$x=\lambda$,
$|y| = 1$,
$z$ = der ganze Rest des Wortes $w$.

$y$ ist also gerade das erste Zeichen des Wortes $w$. Offenbar sind die drei Eigenschaften so erfüllt. Und nun kann es immer noch zwei Fälle geben: Entweder ist $y=a$ oder $y \neq a$. Ist $y=a$, gilt $$w=a^\star b^nc^n \in L_1$$ Pumpen wir nun zu $xy^iz$, verändern wir nur die Anzahl an $a$'s, also bleiben wir in der Sprache (das muss in dieser Beweisrichtung für alle $i$ gelten, hier dürfen wir uns also kein $i$ aussuchen!).

Ist dagegen $y \neq a$, ist das Wort $$w=b^\star c^\star \in L_1$$ Egal, ob es dann überhaupt $b$'s gibt oder nicht, ob also $y=b$ oder $y=c$, die relative Anzahl an $b$'s und $c$'s ist im Fall, dass es keine $a$'s im Wort gibt nicht spezifiziert, also bleibt jedes beliebige $xy^iz$ in der Sprache.

Damit sind wir fertig: Für jedes Wort $w$ ab einer gewissen Größe gibt es eine Zerlegung mit (1), (2) und (3) erfüllt.

Beantwortet: PPL Erklärung

Sat, 09 Jan 2016 17:10:41 +0000

Hallo uzdoa,

Anhand des Bildes (Beispielaufgabe und Lösung) wird das PPL für regläre Sprachen vllt. etwas deutlicher.

Wichtig ist, dass sich der Abschnitt "Daraus folgt" tatsächlich aus den Forderungen (obendrüber) ergibt. Mit etwas formalem Verständnis, sollte das dann nachvollziehbar sein.

Da $ x = 0^{j-k} $ , $ y = 0^k $ und $ z = 0^{n-j} 1^{2n} $ (durch obige Anforderungen) ergeben sich für $ i = 2 $ die letzen beiden Abschnitte.

Da $x y^2 z $ nicht Teil der Sprache $ L_6 $ ist, aber von einem EA, der $ L_6 $ verarbeiten sollte erkannt würde, kann $ L_6 $ nicht von einem EA akzeptiert werden.

Viel Erfolg,

Marvin (Tutor)

Beantwortet: Tutorium 3, HU-3-4

Sat, 09 Jan 2016 00:18:39 +0000

Hallo uzdoa,

jede von einem endlichen Automaten ("genügend lange") erkannte Sprache (da sie von einem EA erkannt wird: reguläre Sprache) besitzt irgendwo eine Pumpstelle (z.B. ein Automat, der folgende Sprache erkennt: $ L_{bsp} = \{ w = (01)^k | k \in \mathbb{N} \} $. Hier kann $ 01 $ beliebig oft gepumpt werden).

Besitzt eine (solche, genügend lange) Sprache nun keine solche Pumpstelle (durch das Pumping Lemma zu zeigen, das PPL ist dann nicht erfuellt) kann es keinen EA geben, der die Sprache erkennt und die Sprache ist nicht regulär.

Beachte: Das PPL gilt nur in diese Richtung, nicht umgekehrt. Das Vorhandensein einer Pumpstelle bedeutet also nicht, dass die Sprache durch einen EA erkannt werden kann.

Hoffe , das konnte zum Verständnis beitragen,

Marvin (Tutor)

Beantwortet: Warum ist L" regulär?

Tue, 22 Sep 2015 06:27:11 +0000

Hallo!

Es stimmt, dass die Sprache $a^n b^n $ nicht regulär ist und dass du dies auch mit dem Pumping Lemma widerlegen kannst.

Allerdings lautet die Sprache L'' ja $b^m c^n $ lediglich mit der Einschränkung $m,n \geq 0$, dh. m und n müssen nicht gleich sein! Genau das ist nämlich das Problem, warum $ a^n b^n$ nicht von einem endlichen Automaten erkannt werden kann: Ein EA kann nicht überprüfen, ob nach der Eingabe von n mal "a"' dann auch genau n mal "b" eingegeben wurde. Diese Einschränkung hat die Sprache L'' aber nicht: hier dürfen auf m mal "b" einfach n mal "c" folgen und die tatsächliche Anzahl der b's und c's ist im Grunde genommen egal ( dh. es ist keine Beziehung zwischen m und n gegeben, die erfüllt sein muss, um ein gültiges Wort der Sprache L'' zu erzeugen).

Natürlich liegt das Wort $ b^n c^n $ auch in der Sprache L'' drin. Wenn du damit nun aber das Pumpinglemma durchführst, dann erhälst du am Ende nach dem Pumpen bspw. den Ausdruck $ b^n+2 c^n $ und dieses Wort liegt ja auch wieder in der Sprache L'' drin, weil wie oben erläutert kein Zusammanhang zwischen der Anzahl der b's und der c's gefordert ist (dh. die Exponenten von b und c müssen insbesondere nicht gleich sein!) Damit liefert das Pumpinglemma für diese Sprache keinen Widerspruch!

Denk aber daran: nur weil das PPL gilt, ist das noch kein Beweis, dass die Sprache regulär ist! Wir können lediglich aus der Nicht-Gültigkeit des PPL schließen, dass dann die Sprache nicht-regulär ist!

In Bezug auf die Aufgabe bedeutet das, dass du der Angabe, dass die Sprache L'' regulär ist, einfach trauen kannst / musst ;)

Ich hoffe, ich konnte dir weiterhelfen!

Gruß, Janine (Tutorin)