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

Beantwortet: verstandnis

Sun, 02 Jan 2022 10:44:26 +0000

Hallo uqyxt,

ja kannst du. Wichtig: Es gilt 0 < k <= j <= n!

Grüße

Jahn (Tutor)

Beantwortet: Alternativer Weg

Tue, 02 Feb 2016 22:43:10 +0000

Hallo uodjt!

Ich glaube du hast einfach nur den ersten Satz der Aufgabe überlesen. Da steht, dass x' gerade die Umkehrung von x ist, also einfach x rückwärts.

Damit ist x = x' durchaus möglich, nämlich dann, wenn x symmetrisch zu sich selbst ist (z.B. x = 000 oder x = 010)

Ich hoffe, das hilft dir weiter!

Viele Grüße,

Janine (Tutorin)

Beantwortet: Zerlegung Pumpinglemma

Wed, 22 Oct 2014 11:17:10 +0000

Bei der Zerlegung w = xyz gilt beim Pumping-Lemma für endliche Automaten, dass xy maximal die Länge n haben darf. Da bei dem gewählten Wort die ersten n Stellen nur aus 0 bestehen, kann xy und damit auch x keine 1 enthalten. Bei dem gewählten Wort muss man nur ein beliebiges Wort >= n wählen, nicht alle Wörter der Sprache.

Viele Grüße

Alexander (Tutor)

Beantwortet: Testwort

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

Die Ableitung funktioniert genauso, wie Sie es vorgeschlagen haben:

S => 0SB => 00SBB => 001SABB => 0011SAABB => 00110SBAABB => 00110S0AABB => 00110S01ABB => ... => 00110S01100 => 00110101100.

Sie können sich jeden beliebigen Teilstring im bisher abgeleiteten Wort nehmen, wenn es eine Regel gibt, auf deren linken Seiter er auftritt, und ihn durch die entsprechende rechte Seite ersetzen. Dabei ist die Position im Wort völlig unerheblich.

Im übrigen könnten Sie das S auch vor dem letzten Schritt ableiten. S muss im Wort nicht vorkommen, damit man weiter ableiten darf - oder besser gesagt: man muss solange ableiten, bis alle Nonterminale verschwunden sind.

Viele Grüße

Lukas König

Beantwortet: Aufgabe b

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

Schau dir mal ein Testwort an.

S-->1S1-->10S01-->10101

Passt doch alles. Es findet eine Umkehrung statt.

Bei dir wäre es:

S-->1S0-->10S10-->10110

Beantwortet: Unterschied der Spracharten

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

Hallo,

die angegebene Grammatik ist ebenfalls korrekt.

Der Unterschied zwischen den verschiedenen Sprachebenen rührt von der Art der Grammatik her, die man zur Erzeugung der Sprache benötigt. Bei regulären Sprachen brauche ich nur eine rechtslineare Grammatik. Bei einer solchen Grammatik steht auf der linken Seite der Produktionen immer ein einzelnes Nonterminalsymbol. Auf der rechten Seite steht entweder das leere Wort, ein einzelnes Terminalsymbol oder ein Terminalsymbol gefolgt von einem Nonterminalsymbol.

Bei einer kontextfreien Grammatik, fällt die Einschränkung der rechtslinearen Grammatik für die rechte Seite der Produktionen weg. D.h. auf der linken Seite der Produktion steht immernoch nur ein einzelnes Nonterminal, auf der rechten kann jedoch eine beliebige Folge von Terminal- und Nonterminalsymbolen stehen - oder auch das leere Wort.

Bei einer kontextsensitiven Grammatik kann zusätzlich auf der linken Seite eine beliebige Folge von (Non-)Terminalsymbolen vor und nach dem eigentlich zu ersetzenden Nonterminalsymbol stehen. Diese muss aber genauso auch auf der rechten Seite der jeweiligen Produktion stehen. Zudem kannst du ein Nonterminal niemals durch das leere Wort ersetzen.

Ich hoffe das hilft dir etwas weiter!

Beste Grüße

Fabian (Tutor)

Beantwortet: Widerspruchbeweis

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

An sich geht man hier genau vor wie bei Aufgabe 34. |y|>0 gilt aufgrund der zweiten Aussage des PPL. y wurde gewählt als y = 0^k mit 0<k<=n. Somit enthält y mindestens eine Null. Wenn man i = 0 wählt, fällt also im vorderen Teil des Wortes mindestens eine Null weg und somit folgt der Widerspruch.

Viele Grüße,

Sven (Tutor)