Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in PUM-AC

verstandnis

Wed, 29 Dec 2021 18:24:31 +0000

Kann ich nur 1<=j <=n und 1<= k <= j sagen statt 0<=k<=j<=n ?

Alternativer Weg

Tue, 02 Feb 2016 19:25:57 +0000

Hallo,

ich wäre hier anders vorgegangen, da ich das x1x' so interpretiert habe, dass x und x' ungleich sein müssten. D.h. ich hätte alle Schritte identisch gemacht , bis auf die Wahl der Pumpvariable, hier hätte ich i=2 gewählt und gezeigt , dass x= x' ist, was nicht Element der Sprache wäre.

i=2:

xy^2z= x^n * 1 * x^n

Falls x=x' von vornherein erlaubt war, dann klärt sich meine Frage von alleine. Danke!

Zerlegung Pumpinglemma

Wed, 22 Oct 2014 11:16:59 +0000

Als w wird ja hier 0^n 1 0^n gewählt. Könnte x aber nicht auch 1^n oder eine beliebige Mischung aus 0 und 1 sein? Kann man das hier einfach frei annehmen?

Testwort

Wed, 22 Oct 2014 11:15:31 +0000

Hallo,

zu Augabenteil c). Ich hab mal versucht ein Testwort zu produzieren.

z.B.: 00110101100

S=> 0SB=> 00SBB=>001SABB=>0011SAABB=> 00110SBAABB

Ich weis nicht wie ich jetzt weiter machen soll. Bzw. ob die Grammatik so korrekt ist. Weil sobald ich jetzt das S ableite wäre ich doch (nach der Grammatik) fertig mit dem Wort. Hätte aber trotzdem noch die restlichen nicht abgeileiteten Nonterminalzeichen im Wort.

also => 001101BAABB

oder kann man einfach weiter ableiten? Bzw. wo fängt man an hinten oder vorne oder ist das egal?

Viele Grüße

Aufgabe b

Wed, 22 Oct 2014 11:13:26 +0000

Zur b)

die Sprache ist doch definiert als x1x' ,

wobei x' eben das Komplement von x ist.

Muss dann nicht:

S --> 1S0 statt S --> 1S1

S --> 0S1 S --> 0S0

S -->1

Unterschied der Spracharten

Wed, 22 Oct 2014 11:11:34 +0000

Wäre bei Teil b) auch folgende Grammatik richtig:

S --> ASA | BSB | 1
A --> 1
B --> 0

Mir ist der Unterschied zwischen den kontextfreien, kontextsensitiven und regulären Sprachen nicht klar. Kann mir jemand in deutschen Sätzen den Unterschied erklären? Mit den Definitonen der Vorlesung kann ich wenig anfangen.

Danke im Voraus

Widerspruchbeweis

Wed, 22 Oct 2014 11:09:43 +0000

Kann man am Ende des Widerspruchbeweises in a) auch vorgehen wie in Aufgabe 34?

i=0
Also wäre w = 0^j-k 0^n-j 1 0^n
= 0^n-k 1 0^n
was also nicht Elemént von L ist.

Wäre das so möglich?

Ich verstehe nämlich die Begründung mit IYI >0 nicht wirklich!