Frag den Hasen

In Fragen suchen


Alte Frage anzeigen
#

Hier beantworte ich Fragen, die mir die Besucher gestellt haben, die aber nicht häufig genug sind, um im FAQ aufzutauchen. Insgesamt wurden bisher 41832 Fragen gestellt, davon sind 42 Fragen noch unbeantwortet.
Wichtig: Es gibt keine Belohnungen für die zigtausendste Frage oder sonst irgendein Jubiläum, Fragen wie "Wie geht's?" werden nicht beantwortet, und die Fragen-IDs unterscheiden sich von der Zahl der gestellten Fragen, weil die Nummern gelöschter Fragen nicht neu vergeben werden. Und welche Musik ich höre, kann man mit der Suchfunktion rechts herausfinden (oder geht direkt zu Frage 127).


Smilies + Codes

Auf vorhandene Fragen kannst du mit #Fragennummer (z.B. #1234) oder mit [frage=Fragennummer]Text[/frage] verlinken.

Hinweis: Es muss Javascript im Browser aktiviert sein, um nicht vom Spamfilter zensiert zu werden.

Zurück zu allen Fragen


#11719
-.- vatan, es sollten natürlich die kontextfreien Sprachen sein.
Puh... Ist hier irgendwie nicht der ideale Ort, um das zu erklären. Das Pumping-Lemma für kontextfreie Sprachen sagt, dass man ein Wort der kontextfreien Sprache, sobald es eine bestimmte Länge hat, in fünf Teile zerlegen kann (also z=uvwxy), und dass man das Teilwort w seinerseits durch vwx ersetzen könnte, ohne dass das Wort aus der Sprache rausfällt. uvwxy ist also drin, uvvwxxy ist drin, uvvvwxxxy ist drin usw.
Im Beweis sieht das so aus, dass eine bestimmte Variable im Ableitungsbaum in einem Pfad mehrfach auftaucht und man die aus dieser mehrfach auftretenden Variable folgenden Teilbäume daher problemlos kopieren und aneinander hängen könnte.