Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in 2014-N-03

Beweisführung bei PPL

Sat, 04 Jan 2020 13:01:04 +0000

Hallo,

1. Frage: Ist das Wort $(111 111)^6$ Teil der Sprache $L$? Ich vermute nein.

2. Frage: Welches konkrete Wort $w \in L$, $|w| \geq n$ wurde in der Lösung gewählt, um zu beweisen, dass die Sprache nicht regulär ist? Ich vermute: $w= |xy^2z| mit$ $i=2$.

3. Frage: Habe ich das richtig verstanden, dass das Wort w hier in x=0, y=w, z=0 zerlegt wurde, da $|xy| \leq n$ und $|y| \geq 1$? Und anschließend würde das Wort $111$ (kleinstes Wort als Bsp.) aufgepumpt $111 111$, nochmal aufgepumpt $111 111 111 111$, usw. (eben immer um die doppelte Länge) lauten. Dieses kann niemals mit der Sprache $111$, $111 111 111$, .... (mit Faktor 3) übereinstimmen. Könnte man hier dann nicht $i = beliebig$ außer 0,1 und 3 wählen und man fällt immer aus der Sprache?

Vielen Dank!

Alternative Lösung

Thu, 12 Jul 2018 17:37:11 +0000

Wäre es hier auch möglich über das Wort $1^{3^{2^{n}}}$ mit $n\in \mathbb{N}$ zu zeigen, dass $L\not\in L_{3}$ ?

Vielen Dank!!

Weshalb ist das kleinste Wort 111

Thu, 21 Jul 2016 14:28:28 +0000

Guten Abend,

vorher wissen wir, dass 111 das kleinste Wort in L ist? In der obigen Definition wird doch von L ⊂ {1}^* gesprochen und es wird nur erwähnt, dass 111 ∈ L ist.

Die gleiche Art von Frage stellt sich mir bei Aufgabe 7 - trotz bisher beantworteter Fragen in der entsprechenden Rubrik!

Kurze erklärung wäre super hilfreich, dank im Voraus!!

Erklärung von Widerspruch

Sun, 14 Feb 2016 09:36:25 +0000

Hallo,

könnten Sie vielleicht die Erklärung bezüglich dem Widespruch mit anderen Wörtern erkären? Ich verstehe nicht so gut wieso da |w| < |xy2z| ≤ 2|xyz| = 2|w| gilt, kommen wir zu einem Widerspruch.

Vielen Dank im voraus!

Pumping Lemma- alternative Begründung richtig?

Sat, 30 Jan 2016 18:02:41 +0000

Wäre es auch möglich hier bei der Begründung das Pumpwort $w =111$ zu wählen, dieses in

$xy = 1^j$, $y = 1^k$, $x = 1^{j-k}$ und $z = 1^{n-j}11$ für $0 < k \leq j \leq n$

zu zerlegen und mit $i = 0$ zu pumpen, sodass das Wort $w' = 1^{n-k}11$ entsteht, welches nicht element $L_3$ ist, da w^|w| gelten muss?

Danke im Voraus!