Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in HU-2-3

Beantwortet: Alternative lösung

Wed, 06 Feb 2019 12:55:37 +0000

Hallo,

ja dein P wäre auch richtig.

Viele Grüße,

Verena (Tutorin)

Beantwortet: b) Alternativlösung

Fri, 25 Jan 2019 16:37:05 +0000

Hallo,

deine Grammatik wäre richtig, wenn die Bedingung i=j+k nicht in der Definition der Sprache enthalten wäre. Durch diese sind nur Wörter erlaubt, bei denen die Anzahl der as am Anfang gleich ist, wie die Anzahl der bs und as im zweiten Teil.

Mit deiner Grammatik könnte z.B. S-->A-->a oder S-->A-->B-->b abgeleitet werden, was allerdings nicht in der Sprache enthalten ist.

Viele Grüße,

Verena (Tutorin)

Beantwortet: Ist meine Alternativlösung so richtig? (Kontextfreie Grammatik Tut 2 Aufg.7 a)

Sat, 19 Jan 2019 15:17:28 +0000

Hallo uvtpu,

deine Lösung ist auch richtig.

Grüße,

Natalie (Tutorin)

Beantwortet: Wizzard fehler / Skript fehler? + Alternativlösung für Kellerautomat möglich?

Sun, 13 Jan 2019 11:10:49 +0000

Hallo unrqo,

leider ist deine Lösung nicht richtig.

Es gibt folgenden Probleme:

1.(s2, a, b) => (s2, lambda) hier muss du den Zustand wechseln. Ein Gegenbeispiel wäre das Wort "abbabaab", das nicht zur Sprache L4 gehört aber von deinem Kellerautomat akzeptiert wird.

2.(s2, b, a) => (s1, lambda) hier ist ein neuer Zustand (bspw. s3) notwendig, ansonst wird eine Schleife gebildet. Gegenbeispiel: das Wort "aababbab".

(Außerdem ist dein Kellerautomat nicht deterministisch wegen den zwei Übergangsfunktionen (s1, b, a) => (s2, ba) und (s1, b, a) => (s1, lambda). Obwohl es keine Anforderung an Determinismus gibt, könnte ein nicht deterministischer Kellerautomaten viele Probleme verursachen, wie eine "Schleife". Deshalb muss man vorsichtig sein, um ein ndet. KA zu bilden.)

3. In der Aufgabestellung m und n sind aus N statt N0, somit wird das leere Wort nicht akzeptiert. Deshalb ist F={s0} falsch.

Ich hoffe ich konnte dir damit helfen.

Viele Grüße,

Runxi (Tutorin)

Beantwortet: Verständnis Übergang

Mon, 26 Nov 2018 23:09:22 +0000

Hallo,

der erste Übergang beschreibt genau die Stelle, an der das i-te a eingelesen wurde und das erste b nun eingelesen wird. An dieser Stelle wirkt die anfangs definierte Idee:

Für alle folgenden b's und a's wird ein Zeichen (in diesem Fall a) aus dem Keller gelöscht, um " i = j + k " sicherzustellen.

Um dies entsprechend zu markieren, wird der Zustandsübergang von s1 zu s2 gemacht.

Der zweite Übergang beschreibt die Situation für alle weiteren eingelesenen b's. Der Kellerautomat bleibt im Zustand s2, solange b's eingelesen werden.

Ich hoffe, es ist klarer geworden.

Beste Grüße

Max (Tutor)

Beantwortet: Alternativlösung?

Fri, 09 Feb 2018 09:24:21 +0000

Hallo,

ja deine Grammatik ist auch korekt.

Liebe Grüße

Verena (Tutor)

Beantwortet: Irregulärer Parse-Baum

Thu, 04 Jan 2018 13:21:51 +0000

Hallo,

du kannst für eine Grammatik, die nicht Lambda-frei ist, keinen regulären Parsebaum angeben, da du am Ende immer eine Ableitung auf ein Terminalzeichen benötigst. Es gibt aber die Möglichkeit einen irregulären Parsebaum anzubegeben, genau wie du beschrieben hast. Für mehr Infos siehe auch diese Frage im Forum:

http://info2.aifb.kit.edu/qa/index.php?qa=5957&qa_1=warum-ist-lambda-für-parsebäume-problematisch

Gruß,

Maren (Tutorin)

Beantwortet: Warum ist lambda für Parsebäume problematisch?

Thu, 30 Nov 2017 08:45:42 +0000

Parsebäume leiten auf unterster Ebene immer in Terminalzeichen ab. Es gibt eigentlich keine Ableitung auf Lambda. Man kann das zusätzlich zulassen (in der Vorlesung machen wir das auch), aber die üblichen Algorithmen sind nicht in der Lage, Ableitungsbäume mit Lambda-Regeln zu erzeugen. Auch der XWizard kann Ableitungsbäume nur erzeugen, wenn es keine Lambda-Regeln gibt.

Der Trick mit dem Pseudo-Lambda-Symbol ist natürlich geschummelt, denn dabei gibt man dem Algorithmus explizit vor, an welcher Stelle er die "Lambda"-Ableitung nutzen soll. Tut man das nicht, ist es im Allgemeinen schwierig zu entscheiden, wo ein Wort erst aufgebaut und dann durch Lambda wieder abgebaut werden kann, sodass am Ende die korrekte Ableitung entsteht.

Ganz allgemein sind verkürzende Regeln immer problematisch und werden, wo es geht, gemieden.

Beantwortet: Anzahl der Zustände

Thu, 02 Feb 2017 19:05:46 +0000

Die Anzahl an benötigten Zustanden ist kein Kriterium dafür, welche Sprache ein Automat erkennt.
Sie können also so viele Zustände benutzen, wie sie wollen.

Beantwortet: 7a Lambda-frei

Thu, 26 Jan 2017 13:41:19 +0000

Ja, das müsste auch gehen, da haben Sie recht. Hier ist noch der XWizard-Link zu Ihrer Grammatik.

Die Fixierung auf das Lambda im Lösungstext sollte nicht bedeuten, dass es ohne Lambda nicht geht, sondern wir wollten hier nur darauf hinweisen, dass normalerweise Parser mit Lambda in der Grammatik nicht umgehen können. Das ist wichtig zu wissen, denn Lambda ist ja im Prinzip in allen kontextfreien Grammatiken zugelassen, aber beim Parsen macht es Probleme. In der PRAXIS lässt man es daher dann doch wieder weg oder macht eine Sonderbehandlung wie wir in der Aufgabe.

Ich werde das beizeiten Umformulieren, Sie haben recht, dass das unnötig verwirrt.

Beantwortet: Alternative Grammatik Aufgabenteil 7b

Sun, 15 Jan 2017 08:37:02 +0000

Hallo,

deine Grammatik ist auch richtig. Sie unterscheidet sich von der Musterlösung eigentlich ja nur dadurch,dass du den Übergang $S \rightarrow A$ "gespart" hast und du zusätzlich einen Übergang $S \rightarrow \lambda$ definiert hast.

Viele Grüße

Julia (Tutorin)

Beantwortet: Verständnis

Tue, 10 Jan 2017 20:37:18 +0000

Hallo,

nein das Wort ba kann mit der Grammatik nicht erzeugt werden.
Der Grund ist, dass immer von S4 aus gestartet werden muss wenn ein Wort gebildet wird.

unter dieser Bedingung ist das kürzeste Wort das gebildet werden kann: abab

Grüße, Sören (Tutor)

Beantwortet: Warum werden neue Zustände eingeführt?

Sat, 07 Jan 2017 18:15:56 +0000

Hallo,

ich kann deine Lösung nicht nachvollziehen, denn wie komme ich in den Zustand s2?

Du brauchst diese zusätzlichen Zustände, um zu gewährleisten, dass deine Wörter die der Kellerautomat erkennen soll von der Form $a^mb^na^nb^m$ sind.

Ich hoffe ich konnte dir weiterhelfen.

Viele Grüße

Julian(Tutor)

Beantwortet: Aufgabe HU - 2 -3 b)

Thu, 01 Dec 2016 16:28:46 +0000

Sie können, wenn Sie die Produktionen / Zustandsübergänge nur ein bisschen anders formatieren, die Grammatik und den Kellerautomaten in den XWizard eingeben und sich die Simulation anschauen. (Tipp für den XWizard: Wählen Sie einfach ein Beispiel aus und passen Sie die Teile an, die Sie anders haben wollen.)

Ihr Kellerautomat: http://www.xwizard.de:8080/Wizz?template=ID-19100

Zugehöriges Skript:

pda:
(S0,a,k) => (S1,ak);
(S1,a,a) => (S1,aa);
(S1,a,a) => (S2,lambda);
(S1,b,a) => (S2,lambda);
(S2,b,a) => (S2,lambda);
(S2,a,a) => (S2,lambda);
(S2,lambda,k) => (S0,k);
--declarations--
s0=S0; /* Startzustand */
F=S0; /* Endzustände */
kSymb=k; /* Bezeichner für $k_0$ */
inputs=aaab; /* Eingegebenes Wort */
--declarations-end--

Dabei sehen Sie auch das Problem, das Julia angesprochen hat: das Wort $aaab$ sollte nicht akzeptierbar sein. Die Grammatik scheint zu stimmen:

Ihre Grammatik: http://www.xwizard.de:8080/Wizz?template=ID-19107

Zugehöriges Skript:

grammar:
S => a, S, a | epsilon | a, X, b;
X => a, X, b | epsilon;
--declarations--
N=S,X; /* Nichtterminale */
T=a,b; /* Terminale */
S=S; /* Startzeichen */
maxdepth=100; /* Maximale Baumtiefe */
maxLengthWords=10; /* Maximale Wortlänge im Baum */
--declarations-end--

Beantwortet: Alternativ-Lösung für kontextfreie Grammatik aus Teil b)

Mon, 08 Feb 2016 14:19:58 +0000

Hey,

das sollte so passen.

liebe grüße,

maren (tutorin)

Beantwortet: Verständnis

Wed, 03 Feb 2016 08:12:35 +0000

Hallo uqdrx,

genau, die Regel $ (s_0, \lambda , k_0) \rightarrow (s_4, k_0 ) $ ist hinzugefügt, dass der Automat auch das leere Wort akzeptiert. Der Kellerautomat wird dadurch aber auch nichtdeterministisch – er kann, falls als nächstes Zeichen ein $ a $ folgt und er sich in Zustand $ s_0 $ befindet "entscheiden", ob er direkt das $ a $ einliest (und die zweite Regel befolgt) oder ein $ \lambda $ "einfügt (und die erste Regel befolgt). Etwas formaler ausgedrückt ergibt sich durch diese "Wahl" ein Konfigurationsbaum, in dem wir alle Möglichkeiten betrachten.

Die Zeile $ (s_1 , a , a) \rightarrow (s_3 , \lambda ) $ sorgt dafür, dass auch Wörter behandelt werden können, die kein $ b $ enhalten. Der Automat macht dies – ähnlich wie die Kellerautomaten, die Palyndrome erkennen – indem er an jeder möglichen Stelle im Wort eine Möglichkeit einräumt, dass gerade die Mitte des Wortes erreicht ist. Deswegen gibt es auch immer eine Konfigurationsfolge, die bei einem Wort mit einer gerade Anzahl an $ a $ in einem Endzustand mit einem leeren Keller endet.

Ich hoffe, ich konnte etwas helfen, wenn nicht, frag' gerne nochmal nach :)

Viele Grüße

Jonas (Tutor)

Beantwortet: erster Lamda-Übergang, um das leere Wort zu akzeptieren

Sat, 30 Jan 2016 15:15:47 +0000

Hallo uedqa,

prinzipiell reicht es bei einem nichtdeterministischen Kellerautomaten nicht, sich nur eine mögliche Konfigurationsfolge anzuschauen, sondern sobald eine Konfigurationsfolge existiert, die nach Abarbeitung des Wortes zu einem Endzustand führt, wird das Wort akzeptiert (siehe VL Folie 3,12). Es ist also "kein Problem", dass es auch eine Konfigurationsfolge gibt, in der das Wort nicht akzeptiert würde, solange es eine andere "akzeptierende" Folge gibt.

Ich hoffe, das beantwortet die Frage...

Viele Grüße

Jonas (Tutor)

Beantwortet: Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Mon, 21 Sep 2015 09:53:59 +0000

nochmal eine Frage zu der Grammatik bei a)

wäre folgende Grammatik auch richtig?

S -> aSb | aAb

A -> bAa | ba

Es ist doch zulässig, auch auf mehrere Terminalsymbole abzuleiten. So spare ich mir eine Zeile und ich stelle sicher, dass m und n >= 1 sind.

Danke!

Beantwortet: Kann man bei KA den Zustand s0 weglassen?

Mon, 21 Sep 2015 09:43:59 +0000

Hallo,

ja das wäre auch möglich. In diesem Fall müsste aber S1 auch noch als Endzustand definiert werden, um auch das leere Wort akzeptieren zu können.

Viele Grüße,

Sebastian(Tutor)

Beantwortet: KA1: wieso nicht mit zwei Zuständen?

Mon, 21 Sep 2015 09:39:24 +0000

Deine Grammatik ist denke ich auch richtig.

Viele Grüße

Christiane (Tutorin)

Beantwortet: Verständnisproblem: Lambda-Übergang & KA nicht deterministisch

Mon, 21 Sep 2015 09:38:17 +0000

Zu b)

1) Ja das stimmt, du kannst mit dem Übergang nur von s0 nach s4, wenn das oberste Kellerzeichen k0 ist.

2) Du meinst die Übergänge

(S1,a,a) --> (S1,aa)

(S1,a,a) --> (S3,lamda), oder? Ja, das hatte ich übersehen, der KA ist also nichtdet.

3) Ich glaube, du hast Recht, dass man die Unterscheidung zwischen s0 und s1 nicht zwingend braucht.

Grüße, Christiane (Tutorin)

Beantwortet: b): Zusammenfassung von s0 / s1 möglich?

Mon, 21 Sep 2015 09:35:43 +0000

Wenn du die Unterscheidung zwischen s0 und s1 nicht hättest, wäre dein Kellerautomat nicht-deterministisch. Er könnte jedes Mal, wenn er eins der i as einliest, mit einem lambda-Übergang in den Endzustand s4 übergehen und würde so ein Wort akzeptieren, was gar nicht zur Sprache gehört.

Viele Grüße

Christiane (Tutor)

Beantwortet: Kann man Übergang S->aSb weglassen?

Mon, 21 Sep 2015 09:33:43 +0000

Hallo,

ich stimme dir zu.

Basti(Tutor)

Beantwortet: 3 Nonterminalsymbole notwendig?

Mon, 21 Sep 2015 09:32:29 +0000

Hallo,

du kannst das nicht machen, denn m und n element der Natürliche Zahlen ohne null sind. Wenn du die Regel änderst, kannst du nicht sicherstellen, dass n nicht null wird.

Beste Grüße

Antonio (Tutor)

Beantwortet: Anzahl und Funktion von Zuständen?

Mon, 21 Sep 2015 09:30:51 +0000

Hallo,

oft merkt man erst beim Konstruieren eines Kellerautomatens, wie viele Zustände man letztendlich braucht. Mit einem Zustandsübergang "speicherst" du eigentlich immer Informationen ab, z.B. darüber, an welcher Stelle eines Wortes sich ein Automat befindet.

In Aufgabenteil a) (wir haben hier übrigens sogar 5 Zustände :) ) bedeutet z.B. ein übergang von s0 nach s1 ( (s0,b,a) --> (s1, ba) ), dass der Kellerautomat alle a's am Anfang des Wortes (a^m) eingelesen hat. Der Wechsel von s1 auf s2 bedeutet, dass er b^n eingelesen hat. im Zustand s2 wird für jedes der n as ein b aus dem Keller gelöscht. Durch Zustandsübergang von s2 nach s3 "weiß" der Automat, dass er nun für jedes der m bs, die er einliest, ein a aus dem Keller löschen muss.

Mit nur 2 Zuständen wüsste der Automat nicht, wann er jetzt as und bs in den Keller reinschreiben, und wann er sie von ihm löschen soll.

Ich hoffe, ich konnte dir helfen!

Christiane (Tutor)