Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in KON-AA

10 Kontextfreie Grammatik Teil 2 Folie GDI2 -107 (Pumping-Lemma für kontextfreie Sprachen)

Sun, 26 Jan 2020 15:14:34 +0000

Mein Frage bezieht sich auf Foliensatz 10 Kontextfreie Grammatik Teil 2, Folie GDI2 -107 (Pumping-Lemma für kontextfreie Sprachen):

Hat es einen bestimmten Grund, dass die Zerlegung hier uvzxy und nicht uvwxy heißt? z wird hier nicht definiert.

Wenn w und z vertauscht werden, dann sollte das auch konsequent geschehen. Zwei Folien später ist nochmal ein ähnlicher Fehler, hier steht "z ∈ L mit |w| >= k"

Algorithmus Grammatik zu Kellerautomat

Mon, 13 Jan 2020 14:06:03 +0000

Hallo,

mich würde interessieren ob der KA, der die gleiche Sprache wie die Grammatik verstehen soll, immer mit 3 Zuständen auskommt, oder ob es Typ-2-Grammatiken gibt, die auch mehr Zustände des zugehörigen KA verlangen?

Falls ja, was beeinflusst die Anzahl der Zustände?

(Frage bezieht sich auf Tut 3)

Danke im Voraus!

Ableiten von Wörtern bei Grammatiken in Chomsky-Normalform

Thu, 11 Jan 2018 21:47:26 +0000

Mir ist aufgefallen, dass in Altklausuren mit Aufgaben zur Chomsky-Normalform häufig in Auggabenteil a) das Umwandeln einer Garmmatik in CNF gefordert ist. Im Aufgabenteil b) soll dann ein Testwort abgeleitet werden, wobei dafür entweder die ursprüngliche Grammatik oder die Grammatik in CNF verwendet werden kann. Da es offensichtlich wenig Sinn macht ein potentiell falsches Zwischenergebnis zu verwenden hätte ich folgende Fragen:

1. Ist es im Allgemeinen einfacher ein Wort mit einer Grammatik in CNF abzuleiten?

2. Gibt es ein strukturiertes Vorgehen zum Ableiten von Wörtern?

Muss man in CNF/GNF umformen können?

Thu, 09 Feb 2017 14:24:00 +0000

Hallo,

muss man für die Klausur eine Grammatik in Chomsky/Greibach Normalform überführen können?

ist Musterlösung eine kontextsensitive Grammatik?

Wed, 26 Nov 2014 14:10:42 +0000

ich dachte, dass eine Kontextfreie Grammatik nur ein Nonterminal Symbol auf der linken seite haben darf.

Meine Lösung ist so

G=(N,T,P,S) N=(S,A) T=(0,1)

S->Lambda|0S|1A

A->1A|1

Für mich sieht die Grammatik in der Musterlösung wie eine kontextsensitive Grammatik aus. Ich denke ich habe da was falsch verstanden bzw. was nicht richtig aus den Folien gelesen. Kann mir da jemand den Unterschied verraten?

Testwort 10101 zulässig ?

Wed, 26 Nov 2014 14:00:47 +0000

Kann aus der Musterlösung auch das Testwort 10101 erzeugen?

Ich denke nicht! Allerdings müsste ein Wort mit eine 1..... auch gehen solange die Anzahl an 1en größer als die der 0en ist.

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

Wed, 26 Nov 2014 13:41:15 +0000

Hier finden Sie eine Auflistung von alternativen Lösungsvorschlägen inkl. Beurteilung aus dem alten ILIAS-Forum (vor WS1415).

Dieser Post wurde der Übersichtlichkeit halber erstellt, um die alternativen Lösungsvorschläge aus dem alten ILIAS-Forum nicht überzubetonen. Wenn Sie neue alternative Lösungsvorschläge diskutieren wollen, sollten Sie eine neue Frage erstellen - und NICHT hier posten!

Allgemeine Vorgehensweise für diesen Aufgabentyp

Wed, 26 Nov 2014 13:39:14 +0000

Hallo,

könnte mir jemand bitte helfen, und sagen, wie ich bei solchen Aufgaben vorgehe, mommentan ist es bei mir ein reines Rate spiel. ICh finde keinen richtigen Ansatz.