Ich bräuchte Hilfe bei folgender Aufgabe:

"Ein fairer Tetraeder T1 mit folgenden Beschriftungen auf den Seiten:

T1 = {1,1,4,4}

T1 wird nun so oft geworfen bis die angehäufte Augensumme mindestens 3 ist. Sei Y die Zufallsvariable, die die Anzahl der Würfe beschreibt. Berechnen Sie P (Y ≤ 2)."

Gesucht ist also die Wahrscheinlichkeit, dass sich innerhalb der max. ersten beiden Würfe eine Augensumme von 3 ergibt. Das wäre ja nur der Fall, wenn man direkt eine 4 wirft oder wenn man eine 1 und dann eine 4 wirft.

Die Wahrscheinlichkeit, dass man eine 4 wirft, ist 2/4 = 1/2. Die Wahrscheinlichkeit für eine 1 und darauf eine 4 ist 1/2 * 1/2 = 1/4.

Wie rechnet man damit nun P (Y ≤ 2) aus?

Hallo! Ich bräuchte Hilfe bei dieser Aufgabe:

"Sei L = {<M> | M akzeptiert, wenn die Eingabelänge durch 5 teilbar ist}. Zeigen Sie durch Reduktion, dass L unentscheidbar ist."

Ich weiß, dass man jetzt einen Widerspruchsbeweis aufstellen sollte, indem man eine bekanntlich unentscheidbare Sprache U auf L reduziert. Dazu nimmt man an, dass L entscheidbar wäre und dafür somit ein Entscheider existiert. Daraus baut man dann eine Entscheider-TM T für diese unentscheidbare Sprache U, was einen Widerspruch erzeugt.

Welche unentscheidbare Sprache sollte man hier bestenfalls benutzen (vielleicht das Wortproblem ATM) und wie würde dann die TM T im Ansatz funktionieren?

Danke!

Hallo, ich bin auf eine schwierige Aufgabe bezüglich des Pumping Lemmas für reguläre Sprachen gestoßen und ich komme nicht weiter bei der Zerlegung eines Wortes s in xyz. Es handelt sich um die Sprache L = {a^n b^m c b^m a | n, m aus den natürlichen Zahlen}.

Ich hatte als s ursprünglich a b^p c b^p a gewählt, aber ich verstehe nicht, wie man hieraus einen Widerspruch formen kann, denn wenn sich y bloß aus a's zusammensetzt, wird das Pumping Lemma hier ja erfüllt.

Danke im Voraus!