Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
116 Aufrufe

erstmal: dass die Aufgabe leicht ist, ist mehr als relativ.

Aufg.a)

1)Es ist klar wie die Wörter von der Gramatik aussehen, und dass sie kontextsensitiv ist, aber wie komme ich darauf, dass sie rechtslinear ist. Und dann auch noch ohne Keller funktioniert?

2)Wir haben doch gelernt, dass zeichen im Keller gelöscht werden, und dann sieht man, dass die Sprache dazugehört. Wie sehe ich denn jetzt dass die Sprache dazugehört?

3)Man kann ja, wie es in der Lsg. steht, die Aufg. auch mit Keller löschen, wie wäre die Lsg. dann? Woher weiß ich wann das Löschen anfängt?

4)Bei der gegebenen Lösung: wo ist der Sinn, dass ich bei der Eingabe von b ständig denn zustand wechsel, soll es mir helfen den Umkehrpunkt zu finden?

 

Vielen Dank

 

in KEL-AF von utdbu utdbu Tutor(in) (107k Punkte)  

2 Antworten

1 Pluspunkt 0 Minuspunkte

1) Man kann sich zu der Sprache schnell einen endlichen Automaten vorstellen, der diese akzeptiert, da die Struktur der Sprache sehr einfach ist (eine EA ist ja quasi ein Kellerautomat, der den Keller nicht nutzt). Daher muss es auch eine rechtslineare Grammatik geben, die diese Sprache erzeugen kann.

2)Diese Frage verstehe ich leider nicht. Zu was soll die Sprache dazu gehören und wie soll das mit dem Löschen von Zeichen aus dem Keller zusammen hängen?

3)Man könnte zum Beispiel, wenn ein b gelesen wird, dieses in den Keller schreiben. Sobald dann das nächste b kommt, kann man das im Keller stehende b wieder löschen. Wenn dann das dritte b kommt geht das wieder von vorne los. Man wüsste dann, dass der Keller nur k0 enthalten darf, wenn das erste a kommt. Sonst würde das Wort nicht akzeptiert werden, da im ersten Teil der akzeptierten Wörter ja eine gerade Anzahl bs steht.

4) Das Wechseln der Zustände codiert, ob eine ungerade oder gerade Anzahl bs zum aktuellen Zeitpunkt eingelesen wurde. Dies muss erfolgen, damit der Automat nur in einen Endzustand gelangen kann, wenn nach einer geraden Anzahl bs die Zeichen aab kommen.

 

von utdbu utdbu Tutor(in) (107k Punkte)  
0 Pluspunkte 0 Minuspunkte

zu 1. Dass es hier eine rechtslineare Grammatik gibt und somit einen Kellerautomaten, der den Keller nicht nutzt, das müssen Sie hier nicht erkennen. Es war nur ein nichtdeterministischer Kellerautomat gefordert. Wenn Sie diesen anders (z.B. mit Verwendung des Kellers) konstruieren, und er richtig ist und  zu den Vorgaben der Aufgabenstellung passt, dann ist das ja auch in Ordnung.

zu 2. Ich gehe davon aus, dass Sie hier überprüfen wollen, ob ein Wort zu einer Sprache gehört, d.h. ob dieses von dem Kellerautomat akzeptiert wird (Akzeptor)? Ob ein Wort zu der gegebenen Sprache gehört oder nicht sieht man daran, ob der Kellerautomat nach Abarbeitung des Wortes in einem Endzustand ist oder nicht. ("Zeichen aus dem Keller löschen" hilft Ihnen beispielsweise die Anzahl von Zeichen zu zählen, vgl. a^nb^n, hilft Ihnen aber nicht zu erkennen, ob ein Wort zu der Sprache gehört oder nicht.)

zu 3. sobald hier das erste a kommt, sollten Sie den Zustand wechseln, um zu gewährleisten, dass nach dem a nur noch genau ein a (dann wäre im Keller genau ein a, welches wieder gelöscht werden könnte) und ein b (der Keller enthielte nur k0) kommt.

zu 4. dieses Kodieren der geraden / ungeraden Anzahl an b's können Sie, wie bereits beschrieben, auch mit Hilfe des Kellers erreichen.

Freundliche Grüße
Friederike Pfeiffer

von utdbu utdbu Tutor(in) (107k Punkte)  
...