Links Ableitung (S 42)

[andras98]

Hi,

Wie macht man eine Links-Ableitung?
Ich hab im Skript nicht wirklich viel darüber gefunden. (nur S42) und aus der werd ich nicht schlau.
Gibts irgendwo eine Step-by-Step Anleitung was man da tut?

mfg

Andreas

[Jimmy]

wenn du schon mal nen Rekursiven Algorithmus gesehen hast, und weisst wie dieser funktioniert dann wirst es sicher schnell verstehen..

also du hast z.B .eine Grammatik mit folgenden Produktionen

S => aS | aSbS | C

und du musst rausfinden ob das Ding da oben mehrdeutig ist oder nicht..
Als Gegenbeispiel nimmst du das Wort aacbc .
Eine Linksableitung bildest du folgendermassen:

S laesst sich in aS produzieren. d.h
S |- aS
somit hast du schon dein ERSTES ZEICHEN VON LINKS gesehen abgeleitet (das "a")

fuer das S in aS kannst du wieder einen Ausdruck deiner Produktion einsetzen z.B. aSbS
also insgesamt

s |- aS |- aaSbS

du hast somit das ZWEITE Zeichen deines Zielwortes (aacbc) abgeleitet. fuer die beiden weiteren Schritte ersetzt du die beiden S durch c (achtung du brauchst 2 Schritte dafuer...zuerst das moeglichst linke S ableiten dann die weiteren...)

im Klartext:

s |- aS |- aaSbS|-aacbS|- aaSbS|-aacbc

das gleiche Wort kann man auch auf eine 2te Art ableiten:

S |- aSbS |- aaSbS |- aacbS |- aacbc

das wars mit dem Beweis..

[andras98]

Danke!

Wie kommt man auf das Gegenbeispiel? Geht es mit jeder beliebigen Zeichenfolge oder wie wählt man das Gegenbeispiel?
Der "Algorithmus" ist mir jetzt klar... ;)

PS: Was kostet einen Nachhilfestunde bei dir ? ;)))) Wennst ML/MPL & DPLL auch sogut erklären kannst dann treffen wir uns sicher noch vor DI ;)

mfg

Andreas

[Jimmy]

das mit dem Gegenbeispiel rausfinden hab ich mich auch zuerst gefragt:

http://hades.gothic.at/iforum/showthread.php?postid=34803#post34803

na gut die if else Methode aus dem Skript kann man wohl schlecht dem Zufall zumuten....:p

aber wennst genau hinschaust auf die gegebenen Produktion hast du
aS und aSbS dass heisst um eine Loesung 2 Mal ableiten zu koennen nimmst sicher mal ein WOrt das mit 2 as beginnt, weil einmal faengst du bei der Ableitung mit aS und einmal mit aSbS gut jetzt hast du ein wort das die Form aaSbS hat.. na gut jetzt suchst eine gueltige Produktion die dem ganzen ein Ende berreitet (weil 2 Loesungen hast ja im Hintergedanken schon gefunden) und eine Produktion die ein Ende erzeugt ist jene die keine Rekursion verursacht sprich das ist das c weil dort kein S vorkommt.... und "im Kopf eingesetzt" fuer die S ergibt das -> aacbc. voila ( ich weiss wenn man mal die Loesung hat ists klingts leicht ) aber vielleicht zur Uebung:


- Zeige dass die folgenden Grammatiken mehrdeutig sind:
a) S => x | SS

b)
Start => Tupel
Tupel => ( Stelle , Stelle )
Stelle => Tupel | Ziffer

c) E => E + E | E * E | ( E ) | id

:) DPLL laesst sich erklaeren, Mal ist schon ein wenig umstaendlicher schriftlich zu erlaeutern....

[edit] Nur Rechtschreibfehler

[andras98]

c) E => E +E | E *E | (E )| id

Das versteh ich nicht ... (von der Angabe aus schon)
Da dürfen +,* auch vorkommen? ... org ...
--
Kann man nur nach links Ableiten oder gibts das andersrum auch?
--

DPLL:
Kannst kurz das Reduce() erklären. So wies im Skript ist komm ich immer auf eine leere Menge (ich reduce einfach nach der Reihe alles bis nix mehr da ist, dass geht ja immer ;((( )

Mal:
Gibts da ein Buch oder so? Das Skript ist dafür ja wieder eine Frechheit ... das kann ja keiner daraus lernen. (mir hats einer mal soso lala gezeigt - also ungefär weiss ich es. wennst ein paar PDF's hättest wo des durchgerechnet ist wäre das spitze .... ;)

DANKE !!! DANKE !!! DANKE !!!

Andreas

[andras98]

a)

w=xx

S |- SS
S |- xS
S |- xx

---------

S |- SS
S |- Sx
S |- xx

Okay?

b)

Tupel
(Stelle,Stelle)
(Tupel,Ziffer)
((Stelle,Stelle),Ziffer)

------

(Stelle,Stelle)
(Tupel,Ziffer)
((Stelle,Stelle),Ziffer)

[Jimmy]

Das versteh ich nicht ... (von der Angabe aus schon)
Da dürfen +,* auch vorkommen? ... org ...


natuerlich da darf alles vorkommen... du musst ja nciht rechnen oder sowas.. du brauchst da auch keine Interpretationen von + oder - das sind lediglich normale Zeichen sowie a betc..


DPLL
gut wie du auf eine Klauselmenge kommst ist wohl klar? Wenn nicht dann kurz ne Rekapituation:
du hast als Angabe eine Ausdruck wie
F1, F2, F3 |= G
wenn dieser obige Ausdruck gueltig sein soll dann muss folgendes gelten
F= (F1 AND F2 AND F3) IMPLIES G
bzw. anders umgeformt
NOT F = F1 AND F2 AND F3 AND -G

gut die einzelenen Fs und das NOT G musst du halt in ner KNF umformen (siehe Regeln im Skript)

Gut das kannst dann als Klauselmenge anschreiben
K={ {A, -B,C,-D} , {......}, {...........} }
sozusagen besteht das K aus mehrerern Untermengen ( und diese Untermengen enthalten die Variablen der Fs in KNF )

Gut next step: Reduce...
(1) Wenn du eine Einerklausel hast? Sprich eine dieser Untermengen besteht nur aus einer Variablen, dann reduziere mit dieser...
(2) wenn nicht dann nimm IRGENDEINER Variable

Sagen wir, wir haben KEINE Einerklausel (siehe PO) dann nehmen wir IRGENDEINE... z.B. A

jetzt wird Reduce(K,A) angewendet....
du schaust in deinen Untermengen wo kommt ein A vor? findest du eine Untermenge wo ein A vorkommt sooo streichst du die KOMPLETTE Untermenge weg.. also diese Untermenge exisitiert spaeter in K' nicht mehr... kommt aller dings das A negiert vor... also hast du eine Untermenge wo es ein -A (NOT A) gibt, dann wird in dieser Untermenge nuuur das -A durchgestrichen den Rest der Untermenge uebernimmst weiter in K'
Bsp:
K = { ........{A,B,-C}, {-A, B, D} ..........}

dann ist nach der Ausfuehrung von Reduce(K,A)

K' = { .......{ B , D } ........ }

den Roten Teil kannst ja streichen (A kommt vor) in der zweiten Untermenge streichst nuur das Gruene, weil das Negal vorkommt

und wenn du irgendwann mal ALLE UNTERMENGEN gestrichen hast (sprich die Variablen mit denen du reduzierst kommen vor) dann hast du am Ende eine leeres K''''' = { }
es kann aber auch vorkommen dass du z.B. diesen Fall hast

K'' = { { -A } , { A } }
jetzt reduzierst du sagen wir mit A
dann schaut dein K''' nach Reduce(K'',A) so aus
K''' { { } }
der Unterschied hier ist .. hier ist K''' NICHT LEER sondern hier gilt:
DIE LEERE MENGE IST ELEMENT VON K'''

das ist genau der Unterschied der uns angeben wird, ob erfuellbar oder nicht erfuellbar..
bei K = { } // K ist leer --> ERFUELLBAR
bei K = { { } } // K enthaelt die leere Menge --> NICHT ERFUELLBAR

Wenn du erfuellbar rausbekommst dann kannst schon aufhoeren.. aber wenn du unerfuellbar rauskriegst musst das GANZE VON Anfang (Anfangsklauselmenge mit dem NEGAT reduzieren ) s.Anfang wir haben mit A reduziert jetzt machst das gleiche mit NOT A ( sprich du redzuierst das gleiche K mit NOT A) und wennd u dann am Ende Erfuellbar rauskriegen solletest dann heisst das:

NOT F ist erfuellbar also ist F nicht gueltig ... (es gibt eine Moeglichkeit wo F falsch ist)

deswegen ist die Konsequenzrelation FALSCH

jetzt ist natuerlich auch ein Gegenbeispiel gefragt..
hmm das ist auch nicht schwer..
du schaust immer auf dei Variablen mit denen du reduziert hast (bei dem Rechenweg, wo du erfuellbar rausbekommen hast)
d.h. sagen wir du hast mit
-A, B , -D C reduziert
dann ist
I(A) = false ... wiesoo?? weil I(-A) = t heisst genauso anders definiert I(A)= false
I(B) = t .... da gibts nicht viel zu sagen
I(D) = f
I(C) = t

Merkregel ueberall wo du ein NOT davor hast schreibst du I(X) = f
wo nix davor steht ein true (t)

Jetzt kanns auch sein dass du Variablen hast die zwar in deinem urspruenglichen K vorkommen aber bei deinen Reduces niiie verwendet wurden sag ma z.B. ein E kommt in eine der Untermengen von K vor aber du hast das nie reduziert (bzw. not E)
diese Variable kannst beliebig setzen z.B. I(E) = t oder false (ist deswegen egal, weil du das sowieso nie reduziert hast..

mfg,
jimmy

[andras98]

also für alle dies nicht wissen Jimmy = Salzer :cool:

Er ist hier nur mit einem anderen Namen und will dass wir alle des beim 4ten Mal schaffen.

Grössten Danke wieder von mir (und sicher auch von anderen die jetzt mitlesen ...)

Werd mir morgen so ein DPLL reinziehen ...

Kannst noch eventuell sagen ob meine Grammtiklösungen stimmen (siehe Posting oben). DANKE :devil:

gn8,

Andreas

[Jimmy]

also für alle dies nicht wissen Jimmy = Salzer


Nein danke ;)

du nimmst bei a) bei der 2ten Herleitung keine Linksableitung... sondern ne Rechtsableitung du ersetzt das x auf der Rechten Seite obwohl du links ein freies S hast.. bei einer Linksableitung musst du von links angehen

ich schick mal wie ichs geloest hab.. aber um die Uhrzeit ;-) kann ruhig einiges falsch sein :)

[andras98]

Hi,


ad DPLL)
wenn man von der PR vom 28.11

F1: not B = D

da kommt bei mir
(not B n D) u (B n not D) wenn ich das in KNF mach würden noch mehr B und D da sein. Der Salzer hat aber nur
{B, D}, {not B, not D}

http://www.logic.at/lvas/thinf1/angaben/ti1v026/5.jpg

Wie kommt er darauf??? die anderen kann ich auch nachvollziehen ...

Automat:

Wie kann er bei der gleichen PR beim Automaten darauf dass er {c,d},{b,c,d} zusammenfassne kann???? die sind ja nicht "gleich"....



http://www.logic.at/lvas/thinf1/angaben/ti1v026/1.jpg

Des wäre echt noch spitze wenn du dass wüsstest .. ;)

DAnke!

Andreas

[Jimmy]

Automat:

Wie kann er bei der gleichen PR beim Automaten darauf dass er {c,d},{b,c,d} zusammenfassne kann???? die sind ja nicht "gleich"....


das ist nicht so schwer...
in deiner "Treppen"tabelle hast du ein LEERES Feld und das ist genau {c,d}, {b,c,d} ..d.h du kannst die beiden zusammenfassen..

[andras98]

aber ...

laut Sigma Dach

ist

-----------|---0--|----1------|-----
{b,c,d} | {d} | {b,c,d}
{c,d} | {d} | {c,d}

und des ist ja nicht gleich ... ich hätt in das leere feld 1 eingetragen ... warum nicht?

[Jimmy]

ja schon klar.... aber die Treppenfunktion hat einfach VORRANG ;)
und wenn du statt {b,c,d} {c,d} einsetzt dann hast du eine Tabelle wie
__________________
| { c , d } { d } { c , d }
| { c , d } { d } { c , d }

[andras98]

Treppenfunktion:

Ich zeichne aus Sigma Dach folgendes in die Funktion ein:

auf der X Achse beginne ich mit dem ersten Wert des Sigma Dachs,
auf der Y Achse trage ich alles ab dem 2 Wert des Sigma Dachs ein.
Dann markiere ich die EZ vs. keine EZ mit Epsilon. Die nun verbleibenden Kästchen schau ich in der Tabelle nach. Bspw. {d} und {a}. Diese unterscheiden sich laut Tabelle bei 0 und 1. => Ich trage 0,1 ein.

Wende ich diesen Alg. an. Sind für mich {c,d}, {b,c,d} unterschiedlich.

Was ist bitte "die Treppenfunktion"?
Wann kann ich was zusammenfassen?
Hab deine obere Erklärung nicht verstanden.({c,d},{b,c,d}

mfg
Andreas

[Jimmy]

Die nun verbleibenden Kästchen schau ich in der Tabelle nach. Bspw. {d} und {a}. Diese unterscheiden sich laut Tabelle bei 0 und 1. => Ich trage 0,1 ein.


nee nee neeeee das hast falsch verstanden..
-in der Ersten Runde tragst die Epsilon ein .. das hast du richtig verstanden..

-in der 2ten Runde schaust du in den freien Knotenpaaren, mit WELCHEM Wort kommst du zu einem Knotenpaar das BEREITS mit einem EPSILON (s.Runde1) markiert ist, findest du ein solches DANN tragst du DIESES Wort ein.

-in der 3ten Runde (falls dir noch freie Kasteln uebrig bleiben - und bei der Pruefung bleiben dir welche) tragst du DAS WORT ein mit welchem du zu einem Knotenpaar kommst, dass bereits mit einem Wort (ACHTUG nicht Epsilon) markiert hast.. Kommst du von einem Knotenpaar z.B. {x},{y} mit dem Wort A zu einem Paar {u},{v} und dieses u,v Paar ist bereits mit einem sagen wir "B" markiert.. dann tragst du im Feld x,y DAS WORT mit dem zum Paar u,v gelangst PLUUS das Wort das in u,v drinnensteht.. also in unserem Fallbeispiel x,y steht jetzt AB drinnen. Weil mit A kommst du zu einem Paar wo bereits mit einem B belegt ist. ->AB

steht in z.B im Paar u,v z.B. Das Wort BA - dann kommt im Feld x,y natuerlich ABA

ich hoffe du hast den Rechenweg verstanden.. Im Skriptum auf S.34 stehts auch drin..

ACHTUNG: Korrektur der Musterloesung..

http://www.logic.at/lvas/thinf1/angaben/ti1v025/1.jpg

ganz unten rechts stand vorher NUR A jetzt gehoert AB (genau aus dem obigen Grund). in seiner urspruenglichen Version ist dem Prof. ein Fehler unterlaufen.. viellecht warst du deswegen so verwirrt ;)

Viel Spass noch,
jim

[bubum]

Kann mir vielleicht wer sagen wann ich weiß, ob der Anfangszustand auch als Endzustand gilt??

mfg

[Jimmy]

Original geschrieben von bubum
Kann mir vielleicht wer sagen wann ich weiß, ob der Anfangszustand auch als Endzustand gilt??

mfg

Wenn du NUR mit Epsilons vom Startknoten zum Endknoten kommst, dann ist der Anfangszustande der Endzustand , weil du unterwegs nix "konsumierst ".

[bubum]

Super, danke für die Hilfe!

mfg

[Neutrino]

Original geschrieben von Jimmy

ACHTUNG: Korrektur der Musterloesung..

http://www.logic.at/lvas/thinf1/angaben/ti1v025/1.jpg

ganz unten rechts stand vorher NUR A jetzt gehoert AB (genau aus dem obigen Grund). in seiner urspruenglichen Version ist dem Prof. ein Fehler unterlaufen.. viellecht warst du deswegen so verwirrt ;)


das ist der beweis: jimmy=salzer
wie sonst waere ihm der einzelne neue Buchstabe auf einer von milliarden seiten im web aufgefallen :-)

nu

[Neutrino]

Original geschrieben von Jimmy


Wenn du NUR mit Epsilons vom Startknoten zum Endknoten kommst, dann ist der Anfangszustande der Endzustand , weil du unterwegs nix "konsumierst ".

ich moechte ja nicht i-tuepfel reiten, aber genau muesste es heissen:
"falls man mit dem epsilon vom startknoten zum endknoten kommt (das leerwort also in der originalsprache drin ist), also egal ob 'NUR' oder auch anders, dann muss man im deterministischen automaten AUCH den startknoten zum endknoten machen (zusaetzlich zu allen knoten des deterministischen automaten, die einen der originalen endknoten enthalten)."

hoffe, der satz ist noch verstaendlich ...

nu

[bubum]

Meine Vermutung: Jimmy=Neutrino= Salzer
:) :)

[Jimmy]

Original geschrieben von andras98
ad DPLL)
wenn man von der PR vom 28.11

F1: not B = D

da kommt bei mir
(not B n D) u (B n not D) wenn ich das in KNF mach würden noch mehr B und D da sein. Der Salzer hat aber nur
{B, D}, {not B, not D}

http://www.logic.at/lvas/thinf1/angaben/ti1v026/5.jpg



ich hab meinen Loesungsvorschlag mal als Anhang gepostet

[andras98]

Falls es jemand interessiert ...

> Haben sie in folgendem Beispiel bei F1 einen Fehler beim Schritt 1: Ersetze
> alle Operatoren durch "und,oder, nicht" gemacht?
>
> F1: -B=(3 strich) D
>
> Da kommen sie auf {B,D},{-B,-D}. Ich aber auf {-B,D},{B,-D}.
> Haben sie versehentlich die Formel A =(3 strich-durchgestrichen) B angewandt
> oder liegt meinerseits ein Fehler vor.

Ich denke, ich habe keinen Fehler gemacht.

1. Loesungsweg:

(-B = D)
= (-B & D) | (B & -D)
= (-B | B) & (-B | -D) & (B|D) & (D&-D)
= (-B | -D) & (B|D)
(da die anderen beiden Klauseln konstant true sind; man koennte sie auch
drinnen lassen, wuerden automatisch wegfallen)

2. Loesungsweg:

(-B = D)
= (-B => D) & (D => -B)
= (--B | D) & (-D | -B)
= (-B | D) & (-D | -B)

Einverstanden?

Gernot Salzer

[Jimmy]

ich denke er hat recht ;-)
Methode 2 ist aber echt schlau....:bounce:

[Filz]

Ich denke die Überdosis an sinnlosen Zeichen hat ihn selbst verwirrt... :)


...
...
= (--B | D) & (-D | -B)
= (-B | D) & (-D | -B)


sollte ( B | D) & ( -B | -D) ergeben