Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in END-AG

Beantwortet: ALTERNATIVE

Fri, 21 Jan 2022 16:30:27 +0000

Hallo uqyxt,

in der Aufgabe ist nach einer rechtlinearen Grammatik gefragt, also sind nur Regeln der Form N->TN | T erlaubt.
Also ist deine Lösung hier nicht richtig. mit dem leeren Wort auf der rechten Seite muss man eventuell auch aufpassen, je nachdem, welcher Typ die Grammatik haben soll.
Zusatz: Anstatt A -> 0B | 1B .. kannst du auch direkt A -> 0A | 1A ... schreiben, das B gibt keinen Mehrwert.

Viele Grüße
Anne (Tutorin)

Beantwortet: Weitere Alternativlösung

Sat, 20 Mar 2021 16:09:51 +0000

Hey, deine Lösung ist auch richtig

Beantwortet: Weiterer Alternativvorschlag

Wed, 11 Jan 2017 13:28:35 +0000

Leider ist eine Grammatik mit dieser Regelmenge nicht rechtslinear, da die Regel $C \rightarrow D$ nicht rechtslinear ist.

Viele Grüße,
Julia (Tutorin)

Beantwortet: Alternative Lösung

Tue, 12 Jan 2016 13:46:31 +0000

Diese Lösung würde insofern nicht gehen, als nach einer rechtslinearen Grammatik gefragt ist, und solche Regeln wie $S \rightarrow 01A$ daher nicht erlaubt sind.

Ansonsten ist Ihre Lösung aber von der Funktionsweise her (wenn ich nichts übersehe) korrekt.

Sie können übrigens auch den XWizard nutzen, um Ihre Grammatik zu untersuchen. Hier ist der Direktlink:

http://www.xwizard.de:8080/Wizz?template=ID-11173#Output

Und hier das zugehörige Skript:

grammar:

A => 1, A | 0, B;

B => 0, B | 1, B | 0, C;

C => 1;

S => 0, 1, A;

--declarations--

e=#n#;

N=S,A,B,C;

T=a,b,c;

S=S;

displayMode=2;

maxdepth=50;

cutNonTerminalBranches=true;

cutTerminalDoubleBranches=true;

maxLengthWords=7;

multiLetterSymbolsHaveIndex=false;

parseTreeNum=0

--declarations-end--

Beantwortet: Noch ein weiterer Alternativlösungs-Vorschlag

Wed, 15 Oct 2014 12:07:49 +0000

Hallo,

nein, diese Grammatik ist nicht ganz korrekt, denn man kann folgendes ableiten:

$S \Rightarrow 0A \Rightarrow 01B \Rightarrow 011 \notin L$

Denken Sie noch etwas darüber nach.

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen und Micaela Wünsche

Beantwortet: Noch ein alternativer Lösungsvorschlag

Wed, 15 Oct 2014 12:06:23 +0000

Ich nehme an, A ist das Startsymbol.

Nein, wegen $C \rightarrow \lambda$ kann man Wörter erzeugen, die nicht auf 01 enden, z.B. 010.

Daneben ist $D \rightarrow 1E$ und $E \rightarrow \lambda$ unnötig kompliziert und kann zu $D \rightarrow 1$ vereinfacht werden (soweit ich informiert bin, gibt es in der Klausur keinen Abzug für unnötig komplizierte Grammatiken/Automaten)

Gruß,

Tobias (Tutor)

Beantwortet: Alternative Lösung - wie geht es kürzer?

Wed, 15 Oct 2014 12:03:30 +0000

Hi,

deine Lösung ist leider falsch. Das Wort 011101 ist Teil der Sprache und wäre mit deinem regulären Ausdruck nicht zu erzeugen. Um den regulären Ausdruck zu erhalten, betrachtet man am besten den nichtdeterministischen Automaten oder die Definition der Sprache, der deterministische Automat ist meistens deutlich komplizierter.

Die Sprache ist so definiert, dass am Anfang und am Ende immer 01 stehen müssen und die Zeichenanzahl mindestens 4 beträgt. Wenn am Anfang und am Ende 01 stehen, ist die Bedingung zur Zeichenanzahl ja schon automatisch erfüllt. Dazwischen können noch beliebige Zeichen stehen, deshalb fügt man im regulären Ausdruck (0 + 1)* ein.

Wenn man den nichtdeterministischen Automaten bretrachtet erkennt man gleichermaßen, dass die Wörter die Form 01(beliebige Zeichen)01 haben und erhält so den regulären Ausdruck.

Gruß,

Jonas (Tutor)

Beantwortet: Leeres Wort Nonterminalsymbol?

Wed, 15 Oct 2014 12:01:58 +0000

Lambda ist weder Terminal- noch Nonterminalsymbol. Es bedeutet einfach, dass ein Nonterminalsymbol auf nichts weiter abgeleitet wrid, also leer ist.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Noch eine alternative Lösung

Wed, 15 Oct 2014 12:00:01 +0000

Hallo.

In deiner Lösung sind mehrere Dinge nicht ganz richtig. Zum einen ist kann mit deiner Lösung das leere Wort erzeugt werden. $S \rightarrow \lambda$!

Außerdem ist nicht gesichert, dass die Wörter länger als 4 Zeichen sind. Deine Grammatik erzeugt z.B. auch die Wörter 0, 1, 011, 00 und viele andere. Damit ist zudem nicht gesichert dass das Wort mit 01 beginnt und endet.

Wichtiger ist allerdings noch, dass du die Regeln für eine rechtslineare Grammatik beachten musst!

Zur Erinnerung: $P_{rechtsnlinear} \subset N \times (T \cup TN \cup \{\lambda\})$

Deine Regel $S \rightarrow 01S$ ist allerdings von der Form "$N \rightarrow TTN$"

Liebe Grüße,

Leonard

Beantwortet: Alternative Lösung auch korrekt?

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

Hallo,

bereits in der ersten Zeile : S --> 01A verletzt du die Regeln für Rechstlineare Grammatiken.

'nur Produktionen der Form: A --> lambda ; A --> a oder A--> aB' vergl.: erstes Kapitel der VL-Folien

In der Aufgabenstellung ist explizit nach einer rechstlinearen G gefragt, somit würde deine G zwar die korrekte Sprache erzeugen aber nicht den korrekten Typ aufweisen.

Das mit dem lambda ist auch nicht so schön, weil es ja auch nicht Element deiner Terminalsymbolmenge ist und somit nicht wirklich ein Terminalsymbol. Somit verstößt du mit deiner Umbenennung (A --> C ) wieder gegen die Rechstlinearität.

Abkürzen könntest du eleganter, indem du gleich die Regel A-->01 hinzufügst - aber Achtung: wieder nicht rechtslinear!

Basti(Tutor)

Beantwortet: Umwandlung von det. EA in rechtslineare Grammatiken

Wed, 15 Oct 2014 11:51:16 +0000

Solange Sie es richtig machen, ist das natürlich ok!

Wenn in der Aufgabenstellung nichts von einer minimalen Lösung, etc. steht, dürfen Sie auch längere Lösungen angeben, ohne dass Punkte dafür abgezogen werden.

Viele Grüße

Lukas König