Pumping Lemma - Beispiele und Tricks

Summary

Dieses Video erklärt das Konzept der Sprachbarriere durch das Pumping-Lemma. Es demonstriert, wie man in verschiedenen Sprachen, die bestimmte Eigenschaften wie die Anzahl der Buchstaben oder die Länge von Wörtern haben, Beweise für die Unkenntbarkeit einer Sprache erstellen kann. Es gibt Tipps zur Wortauswahl und zur Vorbereitung auf Herausforderungen im Pumping-Lemma-Spiel, um zu zeigen, dass die Sprache nicht durch Pumping erkannt werden kann, unabhängig von der Gegner-Aktion.

Takeaways

• 😀 Das Video behandelt das Konzept der Sprachpumping, wobei die Unkenntlichkeit von drei verschiedenen Sprachen demonstriert wird.
• 🔍 Die erste Sprache besteht aus Wörtern, die mehr Buchstaben 'a' und 'b' haben, als es im Wort vorkommt. Die Reihenfolge der Buchstaben ist dabei beliebig.
• 🎲 Um die Unkenntlichkeit der Sprache zu beweisen, wird ein strategisches Spiel vorgestellt, bei dem es darum geht, ein Wort zu wählen, das durch Anpassung nicht mehr in der Sprache ist.
• 📚 Die zweite Sprache ist geprägt von immer größer werdenden Lücken in den Wortlängen, was sie nicht regulär macht.
• 📉 Die dritte Sprache hat eine ähnliche Eigenschaft wie die zweite, jedoch mit Lücken in Primzahlen. Hier wird gezeigt, dass durch das Aufpumpen des Wortes seine Länge nicht mehr primzahlig ist.
• 🤔 Die Strategie zur Überwindung des Pumping-Spiels besteht darin, ein Wort zu wählen, das fast nicht mehr in der Sprache ist, und es leicht zu verändern.
• 📈 Ein Tipp ist, ein Wort zu wählen, dessen Länge größer ist als die Länge des nächsten längeren Wortes in der Sprache, um eine Lücke zu schaffen.
• 📊 Die Verwendung von Quadratzahlen als Längen von Wörtern in der Sprache wird als Beispiel genutzt, um zu zeigen, dass durch das Verdoppeln der Länge des Wortes seine Unkenntlichkeit erreicht wird.
• 📚 Die Verwendung von Primzahlen als Längen von Wörtern wird ebenfalls genutzt, um zu zeigen, dass durch das Aufpumpen des Wortes seine Länge nicht mehr primzahlig ist.
• 📘 Es wird empfohlen, ein Wort zu wählen, dessen erste p Buchstaben alle gleich sind, um die Zerlegung des Wortes zu erleichtern und die Unkenntlichkeit zu beweisen.
• 📙 Einige der genannten Sprachen haben die Eigenschaft, dass sie beliebig große Lücken in den Wortlängen aufweisen, was für viele weitere Sprachen eine Strategie darstellt, um ihre Unkenntlichkeit zu beweisen.

Q & A

Was ist das Hauptthema des Videos?

Das Hauptthema des Videos ist die Demonstration, dass bestimmte Sprachen nicht erkennbar sind, indem man die Pumping-Lemma-Methode anwendet.

Was versucht der Sprecher im Video, zu zeigen?

Der Sprecher versucht zu zeigen, dass er ein Spiel gewinnen kann, indem er Wörter aus einer Sprache auswählt, die nicht erkennbar sind, unabhängig davon, was der Gegner tut.

Wie wählt man das Wort aus, das man am Ende des Pumping-Lemma-Beweises verwendet?

Man wählt ein Wort, das zwar in der Sprache ist, aber so ähnlich zu einem Wort ist, das nicht in der Sprache ist, dass man leicht aus der Sprache herauskommt.

Was ist die Idee hinter dem ersten Beispiel der Sprache, die nur Wörter mit mehr als einer bestimmten Anzahl von Buchstaben hat?

Die Idee ist, dass man ein Wort wählt, das zwar in der Sprache ist, aber durch Hinzufügen oder Entfernen von Buchstaben nicht mehr in der Sprache ist.

Wie kann man das Pumping-Lemma anwenden, um zu zeigen, dass eine Sprache nicht erkennbar ist?

Man muss zeigen, dass man das Spiel immer gewinnen kann, indem man Wörter auswählt, die nicht in der Sprache sind, unabhängig von der Auswahl des Gegners.

Was ist die Eigenschaft der zweiten Sprache, die im Video erwähnt wird?

Die zweite Sprache hat die Eigenschaft, dass Wörter in ihr immer größeren Lücken in der Wortlänge haben, was bedeutet, dass es keine reguläre Sprache ist.

Wie kann man die Lücken in der Wortlänge einer Sprache ausnutzen, um zu zeigen, dass sie nicht erkennbar ist?

Man kann zeigen, dass es Wörter gibt, die eine Länge haben, die größer ist als die Länge des nächsten größeren Wörter in der Sprache, was die Sprache nicht regulär macht.

Was ist der Trick im dritten Beispiel, um zu zeigen, dass eine Sprache nicht erkennbar ist?

Der Trick ist, ein Wort zu wählen, das eine Primzahllänge hat, und dann die Länge des Wortes durch Pumpen des Ypsilons auf eine Länge zu bringen, die keine Primzahl mehr ist.

Was sind die Tipps, die der Sprecher für Pumping-Lemma-Beweise empfiehlt?

Der Sprecher empfiehlt, Wörter zu wählen, die fast nicht mehr in der Sprache sind, eine Skizze des Wortes zu machen, die Wortlängen mit immer größeren Lücken zu überprüfen und oft Null oder Zwei zu wählen, um das Wort leichter zu ändern.

Wie kann man die Pumping-Lemma-Methode anwenden, um zu zeigen, dass eine Sprache mit Primzahlen und Lücken nicht erkennbar ist?

Man kann zeigen, dass man ein Wort wählt, das eine Primzahllänge hat, und dann die Länge des Wortes durch Pumpen auf eine Länge bringt, die keine Primzahl mehr ist, indem man die Lücken zwischen den Primzahlen ausnutzt.

Outlines

00:00

😀 Einführung in das Pumping-Lemma

Dieser Absatz stellt das Thema des Videos vor: das Pumping-Lemma. Der Sprecher möchte zeigen, dass bestimmte Sprachen nicht erkennbar sind, indem er Beispiele aus drei verschiedenen Sprachen präsentiert. Er erklärt, dass die Auswahl der Wörter und die Anwendung von Pumping-Strategien entscheidend sind, um zu beweisen, dass eine Sprache nicht regulär ist. Er betont die Bedeutung der Kreativität bei der Auswahl der Wörter und gibt allgemeine Tipps, wie man vorausschauend agieren kann, um das Pumping-Spiel zu gewinnen.

05:01

😉 Anwendung des Pumping-Lemmas auf eine Sprache mit wachsenden Lücken

In diesem Absatz wird das Pumping-Lemma auf eine Sprache angewendet, die Wörter mit immer größer werdenden Lücken in der Wortlänge hat. Der Sprecher erklärt, dass Sprachen, die beliebig große Lücken in der Wortlänge aufweisen, nicht regulär sind. Er demonstriert, wie man durch die Auswahl eines Wörters, das eine bestimmte Länge hat, und die Anwendung von Pumping-Strategien zeigt, dass das Wort nicht in der Sprache enthalten ist. Er verwendet das Beispiel einer Sprache, die Wörter mit quadratischen Zahlen als Längen hat, um zu zeigen, dass diese Sprache nicht regulär ist.

10:02

🎓 Beweis für Sprachen mit Primzahl-Lücken

Der Sprecher präsentiert einen Beweis für Sprachen, die Wörter mit Lücken in Primzahlen haben. Er erklärt, dass, wenn eine Sprache beliebig große Lücken in Primzahlen hat, sie nicht regulär ist. Er demonstriert, wie man durch die Auswahl eines Wörters, das eine Primzahllänge hat, und die Anwendung von Pumping-Strategien zeigt, dass das Wort nicht in der Sprache enthalten ist. Er verwendet das Beispiel einer Sprache, die Wörter mit Primzahl-Längen hat, und zeigt, wie man durch das Pumpen des Wortes die Länge verändert, um zu beweisen, dass das Wort nicht in der Sprache ist.

15:04

🔍 Zusammenfassung der Pumping-Strategien

In diesem letzten Absatz fasst der Sprecher die verschiedenen Pumping-Strategien zusammen, die im Video vorgestellt wurden. Er empfiehlt, Wörter zu wählen, die fast nicht mehr in der Sprache sind, indem man einen kleinen Teil des Wortes ändert oder auf- oder abrundet. Er betont die Bedeutung von Diagrammen, um den Überblick über die Struktur des Wortes zu behalten. Er erklärt, dass es oft ausreicht, das Wort leicht zu ändern, um zu zeigen, dass es nicht in der Sprache ist. Er hoffentlich, dass die Tricks für das Pumping-Spiel verständlich präsentiert wurden und lädt die Zuschauer ein, Feedback zu geben, wenn etwas unklar war.

Keywords

💡Pumping Lemma

Das Pumping Lemma ist ein mathematisches Konzept, das in der Theorie der formalen Sprachen verwendet wird, um zu zeigen, dass bestimmte Sprachen nicht regulär sind. Im Video wird das Pumping Lemma als zentrales Werkzeug eingesetzt, um zu demonstrieren, dass die gezeigten Sprachen nicht durch reguläre Ausdrücke erkannt werden können. Das Lemma wird in verschiedenen Beispielen angewendet, um die Unmöglichkeit der Erkennung zu beweisen.

💡Sprache

Im Kontext des Videos bezeichnet 'Sprache' eine formale Sammlung von Wörtern, die nach bestimmten Regeln gebildet werden können. Die Diskussion dreht sich um die Eigenschaften solcher Sprachen und wie man sie mit dem Pumping Lemma als nicht regulär identifiziert. Beispielsweise werden Sprachen mit 'beliebig großen Lücken' in Wortlängen thematisiert.

💡Zeichen

Zeichen sind die Grundelemente, aus denen Wörter in formalen Sprachen bestehen. Im Video werden Zeichen wie 'a' und 'b' verwendet, um Beispielwörter zu bilden und die Anwendung des Pumping Lemmas zu veranschaulichen. Die Anzahl der Zeichen bestimmt oft die Struktur und die Komplexität der Sprache.

💡Wortlänge

Wortlänge bezieht sich auf die Anzahl der Zeichen in einem Wort. Im Video wird gezeigt, dass Sprachen mit immer größeren Lücken in den Wortlängen nicht regulär sind, was durch das Pumping Lemma belegt wird. Die Wortlänge ist entscheidend für die Anwendung des Lemmas und die Erkennung von Mustern in Sprachen.

💡Quadratzahlen

Quadratzahlen sind Zahlen, die als Quadrat einer natürlichen Zahl dargestellt werden können. Im Video werden Quadratzahlen als Beispiel für eine Eigenschaft von Sprachen verwendet, die durch das Pumping Lemma als nicht regulär gezeigt werden kann, wenn sie in aufsteigender Folge vorkommen.

💡Primzahlen

Primzahlen sind Zahlen, die nur durch 1 und sich selbst ohne Rest teilbar sind. Im Video werden Primzahlen genutzt, um eine Sprache zu definieren, die Wörter einer bestimmten Länge enthält, gefolgt von einer Sequenz von Nicht-Primzahlen, was zu einer nicht regulären Sprache führt.

💡Zerlegung

Zerlegung bezieht sich auf das Aufteilen eines Wortes in seine Bestandteile, die in dem Zusammenhang des Pumping Lemmas als x, y und z bezeichnet werden. Im Video wird gezeigt, wie durch die Zerlegung und Wiederholung von y die Wortlänge manipuliert wird, um die Unregelmäßigkeit nachzuweisen.

💡Kreuzfrei

Ein Wort ist kreuzfrei, wenn es keine Untersequenz hat, die ein vorgegebenes Muster bildet. Im Video wird das Konzept der Kreuzfreiheit verwendet, um zu zeigen, dass bestimmte Wörter, die durch das Pumping Lemma manipuliert werden, nicht in der definierten Sprache vorkommen können.

💡Pfad

Ein Pfad in der Sprachtheorie bezieht sich auf die Reihenfolge, in der die Zeichen in einem Wort angeordnet sind. Im Video wird der Pfad verwendet, um zu erklären, wie die Reihenfolge der Zeichen in einem Wort durch das Pumping Lemma beeinflusst werden kann.

💡Reguläre Sprache

Eine reguläre Sprache ist eine formale Sprache, die durch einen endlich automatisierten Prozess erkannt werden kann, typischerweise durch einen endlichen Automaten. Im Video werden Eigenschaften gezeigt, die verhindern, dass eine Sprache als regulär erkannt wird, indem das Pumping Lemma angewendet wird.

💡Kreuz

Im Video wird 'Kreuz' verwendet, um die Anzahl der Zeichen zu beschreiben, die in einem Wort vorkommen, aber nicht in der erlaubten Reihenfolge. Die Verwendung von 'Kreuz' im Zusammenhang mit dem Pumping Lemma zeigt, wie die Anzahl der 'Kreuz' in einem Wort manipuliert werden kann, um seine Zugehörigkeit zu einer Sprache zu verändern.

Highlights

Video erklärt das Pumping Lemma in drei verschiedenen Sprachen.

Zeigt, dass die Sprachen durch das Pumping Lemma nicht erkennbar sind.

Erklärt das Paradigma des Pumping Lemmas für beliebige Sprachen.

Gibt Tipps für kreative Anwendung beim Wählen von Wörtern.

Beschreibt die Bedeutung der Wortauswahl und der Wortzerlegung im Beweis.

Veranschaulicht die Anwendung des Pumping Lemmas mit Beispielen.

Erklärt die Strategie, ein Wort zu wählen, das fast nicht mehr in der Sprache ist.

Diskutiert die Bedeutung von Wortlängen und deren Anordnung in der Sprache.

Zeigt, wie man die Bedingungen des Pumping Lemmas ausnutzen kann.

Gibt Beispiele für Sprachen mit speziellen Eigenschaften, die im Beweis verwendet werden.

Erklärt, wie man die Wortlänge manipuliert, um die Sprache unkenntlich zu machen.

Veranschaulicht die Verwendung von Quadratzahlen in der Sprache als Beispiel.

Beschreibt die Eigenschaften von Sprachen mit immer größer werdenden Wortlücken.

Erklärt die Anwendung des Pumping Lemmas bei Sprachen mit Primzahlen.

Gibt einen Trick vor, wie man ein Wort auswählt, das leicht aus der Sprache herauskommt.

Diskutiert die Vorgehensweise bei der Wortzerlegung im Rahmen des Pumping Lemmas.

Erklärt, wie man die Länge von Wörtern manipuliert, um die Sprache unkenntlich zu machen.

Gibt einen Trick vor, wie man die Wortlänge durch das Pumpen verändert.

Veranschaulicht die Anwendung des Pumping Lemmas bei Sprachen mit zufälligen Wortlängen.

Erklärt, wie man die Eigenschaften von Sprachen nutzt, um das Pumping Lemma zu umgehen.

Gibt einen Überblick über die verschiedenen Tricks und Taktiken im Pumping Lemma Beweis.

Transcripts

herzlich willkommen zu einem weiteren

video über das pumping damals ich möchte

in diesem video von drei sprachen zeigen

dass sie nicht erkennbar sind und zwar

werden dass diese drei sprachen hier die

ich einmal so repräsentativ ausgewählt

habe also die beweise werden nicht immer

genau gleicher ich habe schon versucht

ein bisschen vielfalt zu bringen und ich

werde dabei auch noch versuchen so ein

bisschen allgemeine tipps zu geben dass

ihr einfach das paradigma für beliebige

sprachen anwenden könnt ja besonders es

gibt ja zwei stellen im beweis nämlich

hier wo wir das wort auswählen müssen

und am ende hier wo wir dass sie

auswählen müssen an diesen beiden

stellen muss man kreativ werden und ich

möchte auch so ein bisschen erklären wie

man da so ein bisschen vorausschauend

sein kann man sich das ein bisschen

einfacher machen kann

ok fangen wir an mit dieser ersten

sprache hier das sind alle worte die

auch aas und bs bestehen die mehr als

bse haben also zum beispiel wird das

wort in der sprache hat sechs aber nur 5

bis dieses wort hier wäre auch in der

sprache ja es ist ja nichts über die

reihenfolge gesagt kann völlig chaotisch

sein hauptsache mehr als als beats und

hier haben wir fünf es aber nur vier bis

ja die buchstaben können auch völlig

geordnet sein zum beispiel erst als dann

alle bis das ist auch in der sprache

denn wir haben hier keine ahnung achters

aber nur zwei bis aber wenn wir

gleichviel sw bs haben oder sogar

weniger als bse dann sind das leute die

nicht in der sprache sind wir wollen

jetzt gleich das pumping lämmer anwenden

um zu zeigen dass diese sprache nicht

erkennbar ist

und dafür müssen wir uns ein bisschen

vorbereiten ja wir müssen ja dieses

spiel hier gewinnen wenn wir zeigen

können dass wir dieses spiel hier immer

gewinnen können ganz egal was der gegner

tut dann ist die sprache nicht erkennbar

das heißt wir müssen uns jetzt

vorbereiten um dieses spiel zu gewinnen

also im gegensatz zum beispiel zur

deutschen nationalmannschaft jetzt bei

der fußball-wm 2018 ja wir müssen uns

vorbereiten wir wollen gewinnen und es

wird ja darauf hinauslaufen dass wir das

wort welches wir hier wählen dass wir

das am ende so ein bisschen auf oder ab

um also einen kleinen teil davon wenn

wir auf oder abrunden ja und damit

wollen wir ein wort erhalten was nicht

in der sprache ist wir müssen also am

besten hier schon ein wort nehmen was

zwar in der sprache ist aber fasten

nicht mehr entsprach

es ist so dass man leicht aus der

sprache raus kommt und da kommt man

jetzt bei dieser sprache hier folgende

idee kommen wir sollen ja mehr als als

bse haben ja das heißt wenn es gleich

viel aus und wenn dann wären wir schon

nicht mehr in der sprache

na dann versuchen wir mal mehr als

bizarr aber nur ein ganz bisschen mehr

ja das wenigste was geht das ist einfach

ein paar mehr als bse wenn der gegner

uns jetzt also das p vorgibt dann wählen

wir jetzt ein wort zumindest nicht

länger p hat aber dass nur ein einziges

am meer hat als bs man könnte man zum

beispiel dieses wort nehmen a hoch +1

bhp denn einmal hat es offensichtlich

länge mindestens prs hat aber noch einen

weiteren vorteil und zwar bestehen die

ersten p symbole nur aus es hier eine

kleine skizze die ersten +1 symbole sind

so alles für uns ist aber wichtig weil

wir diese bedingungen hier haben die

ersten beiden teile der zerlegung der

jetzt gleich kommt diesen höchstens

fehlern

das heißt wir wissen xy werden sich

irgendwo hier unter den mars befinden

und das ist gut denn dann haben wir

kontrolle über die ars wir können dann

also gleich hier im letzten schritt dass

sie gleich null setzen und damit quasi

hier die nase raus streichen ja das y

weglassen und damit haben wir dann die

anzahl derart verringert während die

anzahl der b s gleich geblieben ist wenn

wir die aber verringern um mindestens 1

schon dann sind wir aus der sprache raus

ja dann haben wir nur noch höchstens

soviel swb es aber nicht mehr mehr als

bse also der gegner da gibt uns jetzt

eine zerlegung von unserem wort und wir

setzen jetzt einfach gleich null weil

das eines y weg und dadurch erhalten wir

ein wort was nicht in der sprache ist

also dann ist dieses wort xz ja wo das y

abgepumpt wurde ist gleich null

das hat dann höchstens so viele wie bse

und das ist nicht mehr in der sprache

denn da brauchen wir beide bedingungen

ja einmal y besteht nur aus wie schon

gesagt ja y befindet sich hier vorne

innerhalb der ersten boje wegen dieser

bedingung und y ist auch nicht leer also

y enthält auch mindestens eine ja hier

wird also wirklich mindestens einer

weggenommen wenn wir über simon

weglassen

damit haben wir das nicht in der sprache

ist ja und damit haben wir das spiel

gewonnen und wir haben gezeigt wir

können es immer gewinnen ja ganz egal

was der gegner von p wählt wir wählen

dieses wort und dann ist es völlig egal

welche zerlegung erwählt wir setzen

einfach ihr gleich null

ja das müssen wir mal zeigen wir können

das spiel gewinnen egal was er

gegenspieler macht so das nächste

beispiel auch in quadrath wobei in eine

natürliche zahl ist ja also das hier

sind worte in der sprache zb einer oder

49 116 es ja immer eine quadrat zahl von

aras hintereinander

ja was aber nicht in der sprache wäre

das sind jetzt 17 es hier 17 ist keine

quadrat zahl ist also nicht in der

sprache so diese sprache hier die hat

eine schöne eigenschaft die wird gleich

ausnutzen können und unserem pammer

beweis denn wörter dieser sprache hier

oder besser gesagt längen von wörtern

dieser sprache haben immer größeren

lücken ja hier wie zum beispiel ein wort

der länge 1 und dann gibt es kein wort

der länge 2 kein wort der länge 3 in der

sprache er ist wieder eines der länge 4

wir haben ja so eine lücke der größe

zweier keine wörter länge 2 keiner

wörter länge 3 hier ist sogar noch eine

größere gekürt ja es gibt keine worte

herr länge 5 6 7 und 8

ja das ist eine lücke der größe 4 dann

wird die nächste lücke ist noch größer

es gibt keine wörter der längen 10 11 12

13 14 und 15

ja das eine lücke der größe 6 wenn eine

sprache beliebig große lücken was die

wort längen von wörtern in der sprache

angeht hat dann ist sie nicht regulär ja

und das wird für viele weitere sprachen

könnt ihr das benutzen zb hoch n

fakultät hoch zwei wochen also es ja so

wie funktioniert das jetzt bei solchen

sprachen mit solchen immer größeren wort

lücken irgendwann da sind die lücken

zwischen worten so groß dass das hier

das ist dann sehr langes wort ja das in

der sprache und ich zeichne mal im

vergleich dazu dass p ein ja also p hat

der gegner dann irgendwie gewählt hp ist

solange das nächst längere wort ist dann

aber sehr viel

länger sagen wir so ja das ist das

nächst längere wort ja das ist ein wort

in der sprache

das ist das nächste längere wort ja

irgendwann ist diese lücke größer als p

und dann können wir folgendes machen wir

wählen in unserem zweiten schritt ja

wenn wir dran sind wählen wir dieses

wort ja wir werden also ein wort das

mindestens länge p hat aber so dass auch

das nächst längere wort um mindestens

länger ist

und dann wird die strategie hier einfach

wir pumpen das wort einmal auf wir

gucken dass einmal auf verdoppeln das y

das y hat aber auch höchstens länge p

das heißt das wort wird länger aber

höchstens so ein stück länger das

aufgepumpt wurde ist also länger als

dieses aber kürzer als dieses und damit

ist es nicht in der sprache

also fangen wir wieder so an p wird uns

gegeben vom gegenspieler welches wort

wollen wir wählen

wir müssen dort werden was mindestens

länge p hat aber so dass die lücke zum

nächst längeren wort in der sprache

ebenfalls mindestens ps und da geht in

dem fall tatsächlich die länge p quadrat

rp quadrat ist größer und man kann sich

auch überlegen machen wir auch gleich

noch das nach pik quadrat die

nächstgrößere quadrat zahl also das wäre

ja dann p + 1 in klammern zum quadrat

dass die differenz also vom quadrat bis

zu plus 1 quadrat dass die größer als ps

so aber jetzt kommt der gegenspieler da

gibt uns jetzt eine zerlegung und unsere

idee war

wir pumpen des ypsilon jetzt einmal auf

das machen wir mit gleich zwei und

zeigen dann dass das wort nicht in der

sprache ist das ist also ihr gleich zwei

betrachten jetzt das wort xy hoch 2 z

die idee war das ist länger als das

ursprüngliche wort so länger als p

quadrat und kürzer als die nächst höhere

quadrat zahlen nämlich kürzer als p + 1

zu quadrat wird diese beiden sachen

gezeigt haben wissen wir dass es nicht

in der sprache ist ja weil das y nicht

leer ist ist xy hoch 2z natürlich länger

als xyz aber das ist unser

ursprüngliches wort und das hatte länge

p quadrat unser wort ist also länger als

p quadrat müssen wir noch zeigen ist es

kürzer

als die nächsthöhere quadrat zahl ok

fangen wir einfach mal umgekehrt an was

ist denn minis für quadrat zahl

das ist sp +1 klammern zum quadrat

das ganze aus multipliziert ist peek war

a plus zwei plus eins

jetzt sieht man das relativ schnell wir

haben ja immer xyz drin

das ist so lang wie quadrat ja und dann

haben wir aber noch ein weiteres y aber

das ist höchstens zu lang wie p hier

haben wir über 2p und noch +1 ja also

dieses wort es so lang wie xyz und noch

mal das wort y dazu das erste hat länge

p quadrat das y selbst hat nach dieser

bedingung hier wieder höchstens länge p

also kleiner gleich p + p und das ganze

ist natürlich echt kleiner als pkw

abschluss zweimal +1 ja ist nur ein p

dazu aber jetzt noch mal hier zu null ab

ehren nochmal einst addieren dann

kriegen wir das raus also p quadrat ist

kürzer als unser wort und das ist

wiederum kürzer als die nächst höhere

quadrat zahl und somit ist dann xyz

nicht in der sprache

ok dann kommen wir zum dritten beispiel

ihr habt wahrscheinlich schon

mitbekommen dass wir in den meisten

fällen gleich null oder rechts frei

wählen

wenn das klappt auch meistens denn

meistens ist das wort halt irgendwie so

geschaffen dass wir hier also das

empfindliche ist sage ich mal wenn man

hier so ein bisschen was ändert ja wenn

man hier innerhalb der ersten p symbole

so ein bisschen weiß nicht ein teil

verdoppelt oder ein bisschen was

wegnimmt dann ist es schon nicht mehr in

der sprache also das könnt ihr euch

ruhig auch als faustregel merken

in den mit vielen fällen gleich null

also sofort ich ein bisschen abpumpen

oder gleich zwei das wort ein bisschen

aufpumpen ja in vielen fällen reicht das

aus hier ist es allerdings ein bisschen

anders

ich werde hier zum beweis zeigen bei dem

wenn man nicht gleich null oder gleich

zweifeln sondern auch mal eine andere

zahl

wobei ich auch gleich dazu sagen muss

diese sprache hier die hat auch wieder

die eigenschaft dass sie beliebig große

lücken hat ja es gibt beliebig große

lücken in primzahlen wenn ihr das ist

oder wenn wir in der lage sein das zu

beweisen dass primzahlen beliebig große

lücken haben

dann können wir genauso vorgehen wie

beim vorigen beispiel ja dann wird ihr

hier in diesem schritt ein wort der

länge m wobei eine primzahl ist so dass

die folgenden p zahlen nach dieser

primzahl alles keine primzahlen sind und

dann werde hier gleich zwei und ihr

gewinnt ja ihr punkt das wort ein

bisschen auf und wird das wort ein

bisschen länger aber es wird nicht so

lange das ist die nächste primzahl

erreicht das können dann machen wir

machen es aber anders

wir werden gleich ein p bekommen dann

wählen wir ein wort ausreichend länger

ja irgend eine primzahl größer als p und

dann kriegen wir eine zerlegung irgendwo

eine zerlegung xyz und jetzt müssen wir

das y so oft aufpumpen dass wir hier

keine primzahl mehr als gesamtlänge

bekommen ja wenn das gepumpt ist also

dass die länge die wir insgesamt

erreichen weil ich dann auch iz dass das

irgendeinen factor hat also denn nicht 1

oder die zahl selbst ist und das kann

man so machen

stellen wir uns mal vor was wäre hätte

genau drei aus gehabt und das z sagen

über 5 das ixs und haben zusammen 87

er selbst hat auch noch ein paar ist uns

eigentlich egal wie viele genau

aber wir pumpen das y jetzt einfach

achtmal auf also wir werden dann dass

sie gleich acht ja wir gucken einfach

wie lange sind ickx und z zusammen

dann hätten wir also das ixs jetzt

würden wir achtmal das y einschreiben

und dann am ende noch das z und wie oft

haben wir gepumpt wir haben so

aufgepumpt wx und z zusammen lang sind

denn dann ist die länge des wortes auf

einmal teilbar

durch die länge von ex und z also die

länge von ex plus die länge von z

denn wir haben hier vorne die länge von

xr hier haben wir jetzt das y stehen

aber wie oft steht dass da das steht

länge von iks plus länge von z mal da

und hier hinten steht nur weil die länge

von z das heißt wir haben ja einmal die

länge von ex plus die länge von z und

noch y weil die länge von ex plus die

länge von z

und das kann man dann ausklammern dann

ist das hier die gesamt ford länge ja

und das sind zwei verschiedene faktoren

wir müssen nur noch dafür sorgen gleich

dass die länge von ex plus die länge von

z

auch wirklich

größer als eins ist und dass das auch

größer als eins ist dann ist die gesamt

wort länge keine primzahl mehr ja dann

ist hier eine zerlegung in zwei faktoren

also wir kriegen nur zwei wege geben

wenn wir wählen jetzt eine primzahl die

mindestens so groß ist aber nicht nur p

sondern p + 2 warum p + 2 ja wir wissen

oops i lon hat höchstens länge p dann

müsse nix und z mindestens länge 2 haben

wir wollten ja dass das das exploit am

ende ein faktor von unserer zerlegung

wird und er muss natürlich mindestens

zwei sein

also werden wir als eine primzahl die

größer gleich p + 2 ist und dann setzen

wir wie gleich ach ja das wort hat

mindestens länge p deshalb primzahl

länge also erfüllt diese eigenschaft ja

jetzt kriegen wir wieder eine zerlegung

gegeben

so und jetzt war die idee wir setzen

dass sie auf länge von ex plus länge von

z

und kriegen dann ein wort was keine

primzahl länger hat ja da wären wir

jetzt die länge von diesem gepumpten

wort angucken

das ist die länge von express die länge

von zepp lussi mal die länge von y

sie ist genau die länge von ex plus die

länge von z und das lässt sich wie

ursprünglich geplant so zusammenfassen

zwei faktoren nämlich länge von ex plus

länge von z und den faktor länge von y

+1 und diese faktoren sind beide größer

als 1 das natürlich auch wichtig ja erst

dann wissen wir dass eine zahl keine

primzahl ist wenn wir sie ein produkt

zerlegt haben mit zwei faktoren die

beide größer als eins sind

warum ist der faktor größer als 1 unser

wort hat mindestens länge plus 2 und das

y hat höchstens p symbole davon

naja da müssen mindestens zwei symbole

auf ickx und z abfallen

und warum hat das hier größe mindestens

zwei oops i lon ist man nicht leer

ja nach dieser eigenschaft hier also hat

ypsilanti mindestens ein und dann noch

einen dazu sind mindestens 2 also ist

die länge von dem gepumpten wort keine

primzahl wenn es keine primzahl ist dann

ist es nicht in der sprache und damit

ist diese sprache ebenfalls nicht

erkennbar

also zusammenfassen noch mal kurz die

tricks die ich euch für palfinger mal

beweise empfehlen kann

ok erster trick wählt euch ein wort das

fast nicht mehr in der sprache ist ja

also ein wort das in der sprache ist

aber wenn ihr vorne einen kleinen teil

ändert ja aufpumpt oder ab kommt dann

bekommt ihr in worten nicht in der

sprache ist denn das machte er

letztendlich ihr werdet vorne im wort

innerhalb der sp symbole werdet ihr

einen teil auf oder abrunden

auch dazu noch ein kleiner tipp macht

euch ruhig eine kleine skizze von dem

wort damit der besseren überblick habt

ja das ist dann viel anschaulicher und

wir können viel schneller sehen passt

das mit diesem wort oder nicht er stelle

sich auch die frage ob die wort längen

die in der sprache vorkommen immer

größere lücken haben ja wenn ja dann

macht es so wie im zweiten beispiel

merkt euch auch ruhig das oft gleich

null also das wort so ein bisschen

abpumpen oder ihr gleich zwei also das

wort ein bisschen aufgehoben mehr

ausreicht habe in sehr vielen fans ist

gleich null oder gleich zwei völlig

ausreichen und nur ab und zu für

kompliziertere sprachen muss man mal ein

anderes wählen und dann noch ein kleiner

trick wer wählt ruhig möglichst ein wort

also wenn das möglich ist bei dem die

ersten p symbole des wortes alle gleich

sind

warum weil das y ja immer innerhalb der

ersten p symbole liegt und dann wird es

viel leichter ersichtlich wie die

zerlegung des wortes nur aussehen kann

wenn ihr daran so die zerlegung bekommt

dann wisst ihr dass xy die bestehen alle

nur aus dem gleichen symbolen und das z

ist der ganze rest ja dass das macht es

sehr einfach vermeidet fall

unterscheidungen im letzten fall ja ja

das also meine tricks fürs camping lama

ich hoffe es war alles verständlich

falls nicht gibt den daumen runter und

wir sehen uns im nächsten video