Fachrat Informatik - Forum

Quoted

Original von vier
ein kumpel von mir und ich haben uns heute mal die mühe gemacht gemeinsam ein klausurenwissen für die theo inf klausur zusammenzustellen.. ist online auf meiner page unter theo inf.. link siehe signatur

Vorbildliche Arbeit
Aber ein paar Anmerkungen habe ich dazu noch:

Seite 1:

Pumping-Lemma für a^ib^i: Im Beweis steht "Da |uv| = n", das muss aber nicht gelten. Man kann nur voraussetzen "|uv| =< n". Also ist uv ein Teilwort von a^n aber nicht unbedingt das ganze Wort a^n. Der Rest des Beweises bleibt trotzdem korrekt.

Seite 2:

Typbestimmung: Versteh ich nicht
Mein Vorschlag:

Seite 3:

LOOP-Programme:
Bei den Wertzuweisungen steht die Zeile "x_i := x_j + c bzw x_i := x_j - c" zweimal hintereinander.
Die Definition der LOOP-Schleife ist nicht ganz korrekt. Es muss heißen "Falls P ein LOOP Programm ist und x_i eine Variable, dann ist LOOP x_i DO P END ein LOOP-Programm."

Zu: http://www-thi.informatik.uni-hannover.d…en/uebung02.pdf

Ohne Gewähr. Würde mich freuen, wenn mich jemand korrigieren könnte, falls nötig.

Aufgabe 1:
Damit die Startvariable nicht auf der rechten Seite einer Produktion vorkommt, fügt man einfach eine weitere Variable hinzu, die in der Produktion die Startvariable ersetzt. Man fügt dann nur noch die Produktion "S -> (neue Variable)" hinzu und gut is.

Aufgabe 2a:
ANZAHL A DURCH 2 TEILBAR : TYP3
(nur die Produktionen, S als Startvariable)

S -> B
A -> a
A -> bA
A -> aB
B -> aA
B -> b
B -> bB

Aufgabe 2b:
ANZAHL A = ANZAHL B = ANZAHL C : TYP1
(nur die Produktionen, S als Startvariable)
S -> aBC
S -> bAC
S -> cAB
A -> a
A -> bAC
A -> cAB
B -> b
B -> bBC
B -> cBA
C -> c
C -> aCB
C -> bCA

Reicht es wenn wir bei Automaten die Zustandsgrafik zeichnen oder müssen wir auch noch mal extra die Überführungfunktion(en) einzelnd aufführen ?

Ich hatte ja nochma bei Matthias Galotta nachgefragt wegen Musterlösungen.

>Wenn wir anfangs die Musterlösungen zu den Theo-Inf-Aufgaben nicht haben
>> sollten, weil sonst die Übungen nicht besucht werden, frage ich mich
>> nun, ob es vielleicht vor der Klausur nun doch möglich sein, dass wir
>> die Musterlösungen der Aufgaben in elektronischer Form bekommen. ???


Es tut mir Leid, aber wir werden die Lösungen nicht veröffentlichen.
Wenn wir nun die Lösungen ins Netz stellen würden, so würde unser Argument
zumindest für spätere Semester nicht mehr greifen, denn dann wäre ja bekannt,
dass Prof. Vollmer die Musterlösungen eh' am Ende des Semesters online
stellt.

Quoted

Original von Cipher
und hier die hoffentlich richtige Aufgabe 2 vom Übungsblatt 3 :



Cipher

Ist 0 nicht auch durch 2 teilbar (rest 0) ?
Da könntest du gleich wieder von Zustand 1 zurück zu Zustand 0, wenn ein a gelesen wird. z0 wäre somit auch endzustand.

Quoted

Original von sr409
Zu: http://www-thi.informatik.uni-hannover.d…en/uebung02.pdf

Ohne Gewähr. Würde mich freuen, wenn mich jemand korrigieren könnte, falls nötig.

Aufgabe 1:
Damit die Startvariable nicht auf der rechten Seite einer Produktion vorkommt, fügt man einfach eine weitere Variable hinzu, die in der Produktion die Startvariable ersetzt. Man fügt dann nur noch die Produktion "S -> (neue Variable)" hinzu und gut is.

Das klappt aber nicht bei Typ-3-Grammatiken, da dort die rechte Seite der Produktionen nicht nur aus einem Nichtterminal bestehen darf.

Eine "allgemeinere" Lösung wäre die folgende:

• Füge der Grammatik ein neues Nichtterminal N hinzu
  
• Für jede Produktion der Form S->... füge eine neue Produktion N->... hinzu
  
• Ersetze jedes auf der rechte Seite einer Produktion vorkommende S durch N
  

Das ganze müßte man jetzt evtl. noch beweisen (je nachdem, ob die Aufgabenstellung dies fordert).

Quoted

Aufgabe 2a:
ANZAHL A DURCH 2 TEILBAR : TYP3
(nur die Produktionen, S als Startvariable)

S -> B
A -> a
A -> bA
A -> aB
B -> aA
B -> b
B -> bB

Korrekt, siehe oben.

Quoted

Aufgabe 2b:
ANZAHL A = ANZAHL B = ANZAHL C : TYP1
(nur die Produktionen, S als Startvariable)
S -> aBC
S -> bAC
S -> cAB
A -> a
A -> bAC
A -> cAB
B -> b
B -> bBC
B -> cBA
C -> c
C -> aCB
C -> bCA

Ist leider nicht richtig. Das Wort "cba" kann beispielsweise durch diese Grammatik nicht abgeleitet werden. (Außerdem ist dies eine Typ-2-Grammatik.)

So sollte es aber klappen:
S -> ABCS
S -> epsilon
A -> a
B -> b
C -> c
AB -> BA
BA -> AB
AC -> CA
CA -> AC
BC -> CB
CB -> BC

(Kann man wahrscheinlich noch ein wenig optimieren.)

Quoted

Original von sr409

Quoted

Original von Cipher
und hier die hoffentlich richtige Aufgabe 2 vom Übungsblatt 3 :

Ist 0 nicht auch durch 2 teilbar (rest 0) ?
Da könntest du gleich wieder von Zustand 1 zurück zu Zustand 0, wenn ein a gelesen wird. z0 wäre somit auch endzustand.

Ja, Null ist durch jede ganze Zahl teilbar, es gilt nämlich:

Eine ganze Zahl b aus Z heißt in Z durch eine ganze Zahl a ohne Rest teilbar, wenn es eine ganze Zahl q gibt, die die Bedingung q*a = b erfüllt.


Der Automat müßte aber eigentlich mit nur zwei Zuständen auskommen:

Seien S0 und S1 die Zustände des Automaten, wobei S0 der Startzustand ist. S0 sei ein außerdem ein Endzustand. Dann sollten die folgenden Zustandsübergänge ausreichen:

S0 -(a)-> S1
S0 -(b)-> S0
S1 -(a)-> S0
S1 -(b)-> S1

Quoted

Original von sr409
Reicht es wenn wir bei Automaten die Zustandsgrafik zeichnen oder müssen wir auch noch mal extra die Überführungfunktion(en) einzelnd aufführen ?

wenn Du nen Automaten definierst, schreibste das 5-Tuepl neben den Graphen.
Z, Sigma, Startzustand und E legst per Schrift fest mit Definition. In der Übung bei cbe reichte es dann noch anzugeben, dass "Delta durch den Graphen gegeben" sei

Quoted

Original von sr409
Reicht es wenn wir bei Automaten die Zustandsgrafik zeichnen oder müssen wir auch noch mal extra die Überführungfunktion(en) einzelnd aufführen ?

Das Zustandsübergangsdiagramm reicht aus.

Danke

Quoted

(Außerdem ist dies eine Typ-2-Grammatik.)

Soweit ich das verstanden habe sidn typ2-grammatiken doch einer untermenge von typ0 bzw typ1 grammatiken. wenn ich nun eine typ2 grammatik verwende, so hab ich doch auch die aufgabe erfüllt, wenn eine typ1 grammatik gefordert ist ?

Quoted

Der Automat müßte aber eigentlich mit nur zwei Zuständen auskommen:

Yep, so hab ich das auch.

Quoted

Original von sr409

Quoted

(Außerdem ist dies eine Typ-2-Grammatik.)

Soweit ich das verstanden habe sidn typ2-grammatiken doch einer untermenge von typ0 bzw typ1 grammatiken. wenn ich nun eine typ2 grammatik verwende, so hab ich doch auch die aufgabe erfüllt, wenn eine typ1 grammatik gefordert ist ?

Ja, deswegen steht der Satz auch nur in Klammern.

Es läßt sich aber zeigen, daß für die Beschreibung der in der Aufgabe angegebenen Sprache mindestens eine Typ-1-Grammatik erforderlich ist (das habt ihr vielleicht in der Vorlesung gemacht).

Quoted

Original von sr409
Danke

Quoted

(Außerdem ist dies eine Typ-2-Grammatik.)

Soweit ich das verstanden habe sidn typ2-grammatiken doch einer untermenge von typ0 bzw typ1 grammatiken. wenn ich nun eine typ2 grammatik verwende, so hab ich doch auch die aufgabe erfüllt, wenn eine typ1 grammatik gefordert ist ?

Second post!

Du hast Recht. Allerdings ist die gegebene Sprache nicht kontextfrei. Also kann es keine Typ-2-Grammatik geben, die sie erzeugt.

Kann mir irgendwer nochmal das Verfahren erklären wie ich von einem NFA zu einem DFA komme ?

Is ja hier gefragt: http://www-thi.informatik.uni-hannover.d…en/uebung04.pdf

Mir leuchtet das in dem "Skript" nicht so ganz ein.

Danke Dann geh ich auch schlafen ...

Hi, die Umwandlung NEA -> DEA ist eigentlich recht simpel, wenn man das Prinzip erstmal verstanden hat:
Also:
Du fängst mit deinem Startzustand Z0 an und guckst dir an in welche Zustände der Auto,at übergeht wenn er eine 0 liest. Du schreibst sie in der Form auf z.B.{Z1,Z2,...}
Eventuell geht er auch nur in einen einzigen Zustand über , dann schreibst du ihn auch so auf z.B. {Z1}
Noch eine Möglichkeit ist dass er in keine Zustamd wechselt, es also keinen Pfeil gibt, dann heißt der Übergeangzustand {Leere Menge} bzw. das Symbol dafür. Jetzt guckst du weiter, was mit der 1 in Zustand Z0 passiert und schreibst es analog auf. Jetzt hast du ja Zustände aufgeschrieben. ABER auch wenn de Zustände z.B. {Z1,Z2,Z3} heißen, so ist dies nur ein Zustand vom DEA, er heißt halt nur so bescheuert. Jetzt guckst du dir einfach immer nur an was für neue Zustände auftauchen, die du vorher nicht betrachtet hast, z.B. {Z1,Z2,Z3} und machst wieder die Betrachtung was passier wenn 0 und 1 eingeben werde. Allerdings überprüfst du in diesem Beispiel wohin 1 von Zustand Z1 aus wechselt, von Zustand Z2 aus und von Zusatnd Z3 aus und matscht das alles in deinen neuen oder auch schon bekannten Zustand (z.B. wenn aus allen drei Zuständen der Übergang nur nach Z0 wechselt, hattest du ja schon). Dies führst du nun analog für alle neu enstandenen Zustände mit allen Terminalsymbole durch und irgendwann tauchen keine neuen Zustände mehr auf. Dann ist dein DEA auch schon so gut wie fertig, du brauchst ihn nur noch zeichen, mit den ganzen Zuständen die aufgetaucht sind, wobei wie gesagt die Namen halt nur Namen sind, auch {Leere Menge} ist nur ein Name für einen Zusatnd, du kannst genauso gut die DEA Zustände Z'1...`Z'n nennen, ist egal...

Noch ne grundsätzliche Anmerkung: Die Potenzmenge der Zustände des DEA ist einfach Terminalsymbole hoch Anzahl der Zustände des NEA. Also bei z.B {0,1} als Alphabet und NEA mit 4 Zuständen 2^4 also 16 mögliche Zustände. Dies ist jedoch wie gesagt nur die Potenzmenge, normalerweise fallen viele Zustände weg, weil sie nie erreicht werden (müssen dann auch nicht gezeichnet werden)

Puh, hoffe du kriegst durch diese merh schlechte als rechte Anleitung keine Zustände

Jethro hats schön erklärt, hier noch ein Bsp für euch:

Danke euch beiden - Ich habe mir jetzt irgendwie ein eigenes Verfahren zusammengereimt, dass lustigerweise immer den minimalsten DTA liefert

Meine Lösung zu http://www-thi.informatik.uni-hannover.d…en/uebung04.pdf wäre also:



DTA soll DFA heissen !

Quoted

Original von sr409
Meine Lösung zu http://www-thi.informatik.uni-hannover.d…en/uebung04.pdf wäre also:

Der NFA ist so in Ordnung, der DFA aber nicht:

Dein DFA erfordert z. B., daß jedes akzeptierte Wort mit 0 beginnen muß. Außerdem kann ein bereits akzeptiertes Wort durch Verlängerung um eine 1 wieder zu einem nicht akzeptierten Wort werden. Beides ist natürlich so nicht richtig.


Ich komme auf folgenden DFA:

Zustände:
S0, S1, S2, S3

Startzustand:
S0

Endzustand:
S3

Zustandsübergänge:
S0 -(0)-> S1
S0 -(1)-> S0
S1 -(0)-> S3
S1 -(1)-> S2
S2 -(0)-> S1
S2 -(1)-> S1
S3 -(0)-> S3
S3 -(1)-> S3

@Joachim: jup, das habe ich auch raus.

Vorgehen zum Minimieren eines DFA:
Gucken, welche Zustände bis zum Endzustand vom Startzustand erreicht werden und die restlichen rausschmeißen. (Erreichbarkeit)
Ferner kann man danach noch überprüfen welche Zustände äquivalent sind und durch einen ersetzt werden können.

Und dann noch eine Frage von mir:

Gibt es eine relativ einfach Methode, wie man aus einer kontextfreien Grammatik einen Kellerautomaten erstellt?
Irgendwie komme ich da nicht klar mit der Umwandlung...


Cipher

Quoted

Original von Spike

Quoted

Original von sebi
6.Übungsblatt 1. Aufgabe

Geben Sie einen Kellerautomaten an, der die Sprache {a^i b^i | i>=1 } akzeptiert

† soll das Kellersymbol sein, § = sigma, e=epsilon

K := ({a,b},{s0,s1,sf},{a,†}, §1, s0,†, {sf})^
mit §1 := {
(s0,e,†,sf,e),
(s0,a,†,s0,a†),
(s0,a,a,s0,aa),
(s0,b,a,s1,e),
(s1,b,a,s1,e),
(s1,e,†,sf,e) }

Fast perfekt! Der Befehl (s0,e,†,sf,e) führt aber dazu, dass das leere Wort von diesem Automaten akzeptiert wird. Da aber nur Wörter mit mindestens einem a und einem b akzeptiert werden dürfen (wegen "i>=1"), ist das leere Wort aber nicht in der Sprache. Der Befehl muss also ersatzlos gestrichen werden. Dann entspricht der Automat exakt der Musterlösung

Aber ginge der Automat nicht noch einfacher?
so zum beispiel:

z0,a,# -> z0,A
z0,b,A -> z0,epsilon
z0,a,A -> z0,AA


Cipher

Quoted

Original von Cipher
Gibt es eine relativ einfach Methode, wie man aus einer kontextfreien Grammatik einen Kellerautomaten erstellt?
Irgendwie komme ich da nicht klar mit der Umwandlung...

"Relativ einfach" ist immer so eine Sache. Relativ wozu?

Es gibt ein paar formale Methoden für die Umwandlung. Aber ich schätze, die werden bereits in der Vorlesung behandelt worden sein. Und viel einfacher als die geht es im allgemeinen Fall nicht ...