Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in KON-AI

Fall N=1

Tue, 09 Jul 2019 15:23:41 +0000

Hallo,

beim Fall N=1, hätte man doch mit S ein Nonterminalsymbol noch im wort (abScc), wenn es nach der Produktion P2 gehen würde. Bräuchte man nicht noch einen Lamda-Übergang. Also müsste doch folgende Produktion S-> lamda | abScc gelten, oder?

VG

Beantwortet: Alternativlösung zu Kontextfreier Grammatik

Fri, 05 Feb 2016 12:54:52 +0000

Hallo,

zunächst folgendes Gegenbeispiel:

Testwort aaabbbb (nicht in der Sprache)

Mit deiner Grammatik wäre es wie folgt abzuleiten:

S -> aAaB -> aaaB -> aaabBb -> aaabbbb

Das Problem liegt im Zusammenspiel von erster und zweiter Regel. Damit ist es möglich, eine gerade Anzahl von a's im Wort zu erhalten (was jedoch die Sprache ausschießt).

Viele Grüße

Max (Tutor)

Beantwortet: Verständnis der Lösung 50 a)

Mon, 01 Feb 2016 16:51:47 +0000

Hallo,

die Sprache enthält nur genau die Wörter, die stets zu Beginn eine ungerade Anzahl a's (2k+1) enthalten und danach 2k b's (gerade Anzahl).

Die Reihenfolge der Buchstaben spielt also eine Rolle, es sind nicht einfach alle Wörter mit insgesamt 2k+1 a's und 2k b's enthalten.

Viele Grüße

Max (Tutor)

Beantwortet: zugehörige menge

Sun, 03 Jan 2016 22:57:13 +0000

Hallo ugemt!

Laut dem verlinkten Aufgabenbuch gilt für den Exponenten k der Sprache L2, dass er Element der Menge N = {1,2,3, ...} ist, und die angegebene Grammatik in Aufgabenteil b) ist somit korrekt!

Viele Grüße,
Janine (Tutorin)

Erneut getaggt: Alternative Lösung mit nur einem Nonterminalsymbol

Sat, 17 Jan 2015 06:48:53 +0000

Ist die Lösung mit p = {S -> a | aaSbb} auch richtig?

(Arbeite mit alten Lösungen)

Beantwortet: Kontextfrei vs Kontextsensitiv

Wed, 22 Oct 2014 11:30:20 +0000

Hallo.

Das ist teilweise richtig. Eine Typ-1-Grammatik heißt auch monotone Grammatik, da die Wörter nicht kürzer werden dürfen. Zudem darf kein λ-Übergang stattfinden, außer S→λ, wenn S sonst auf keiner rechten Seite auftritt. (S kann also nur als erste Regel ausgeführt werden).

Für den zweiten Teil deiner Frage gilt, dass jede Sprache vom Typ i auch vom Typ i-1, für i=1,2,3 ist.

Liebe Grüße,

Leonard (Tutor)

Alternative Lösung zu a)

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

Ist diese Lösung auch korrekt:

{

s->a|aAb

A->aSb

}

Danke

Hallo,

Würde auch

S -> aA

A -> aBb | lambda

B -> aAb

gehen?