Fachrat Informatik - Forum

Also das Problem was du schilderst, taucht so garnicht in der Aufgabe auf?!

Also ich hatte kein Problem das die Nichtterminalen Zeichen nicht zu der leeren MEnge führten. Vielelicht kannst du das Problem doch mal an der aktuellen Aufgabe schildern. Also die Produktion angeben wo es nicht geht. Vielleicht sieht man dann ehr nen Fehler?!

Die ursprüngliche Produktion sieht ja so aus:
• S → Bc | dB | AcA
• A → Dd | epsilon | fCBa
• B → acB | acCf | ba
• C → Cef | cDa | epsilon
• D → DfC | eDa | e
Man sieht, dass z.B. bei D -> DfC eine Linksrekursion steht, die ja z.B. zu D -> fCD' wird.
Nun gibt es aber auch A -> Dd | fCBa , also sozusagen wäre nach Einsetzen von D die Produktion A -> fCD' | fCBa
Also zweimal f als Präfix.
Oder mache ich da einen Denkfehler irgendwo?

EDIT:
Oha... sehe gerade einen Denkfehler:
D -> fCD' ist ja so garnicht richtig...
D' -> fCD' wäre das wohl eher... und dann gäbe es nur hinter den anderen D Produktionen ein D'... und schon kein f mehr da.
Ich versuche mal, ob ich so weiterkomme...

EDIT2:
Ok, das Problem ist wohl entstanden, weil ich aus der ursprünglichen Produktionsregel
D -> DfC | eDa | e ein D -> DfC | eDa | epsilon gemacht habe (sah zu ähnlich aus ).
Dadurch wurde dann epsilonD' statt eD' erzeugt, wodurch das f als Präfix auftauchte.

Nicht zu jeder kontextfreie Grammatik gibt es eine LL(1) Grammatik

edit: Ich hasse das neue Forum ... da übersieht man einfach zu schnell, dass der Thread noch ne Seite hat ...

Zum aktuellen Übungsblatt habe ich wieder eine Frage:
In der Übung heute wurde uns gesagt, dass bei der Unifikation ausschließlich eine Variable durch einen größeren Ausdruck ersetzt werden kann.
Also z.B. :
t = x ( alpha , list ( integer ) )
u = x (list ( double ) , list (integer ) )
Da kann dann alpha -> list (double) gesetzt werden.
Aber jetzt das Problem im folgenden Beispiel:
t = x ( alpha , x ( beta , integer ) )
u = x ( list(gamma) , x ( delta , beta ) )
Hier kann zunächst alpha -> list(gamma) gesetzt werden.
Aber dann kommt das Proble, dass beta -> delta ersetzt werden müsste (oder umgekehrt)
und dann beta -> integer (oder delta -> integer).
Dies würde meiner Meinung nach kein Problem sein, aber wie gesagt: in der Übung wurde uns gesagt,
dass ausschließlich eine einzelne Variable zu einem "größeren" Ausdruck wie list(gamma) oder x(beta,delta) usw.
umgewandelt werden kann.

Im Skript steht:
"Einer der beiden Terme ist eine Variable x, der andere Term sei t."
• Ist x = t, dann gebe Sid zurück.
• Tritt x in t auf, so beende den Algorithmus. t1 und t2 sind nicht unifizierbar.
• Sonst gebe die Substitution {x → t} zurück.
Die Frage ist: Darf t auch eine Variable sein oder nur ein "großer" Term?
Denn auf dem Übungsblatt taucht häufiger mal ein Fall auf wo eine Variable durch eine andere ersetzt werden könnte/sollte.
Wurde uns in der Übung also etwas Falsches beigebracht oder kann ein Fall Variable -> Variable tatsächlich nicht aufgelöst werden?

wie ist denn die Definition eines Terms? Ich vermute ja, dass eine Variable ein Term ist und somit eine Substitution Var.->Var. zulässig ist?!?

Im Skript steht vor dem Algorithmus:
Gegeben seine zwei Terme t1 und t2 über einem Variablenalphabet V und einem Alphabet F von Funktionssymbolen.
Und dann folgt später:
Fall 1: Einer der beiden Terme ist eine Variable x, der andere Term sei t.
Und noch später:
Fall 2: Es sei t1 = f (x1 , . . . , xn ) und t2 = g(y1 , . . . , ym ).

Ich denke also, dass ein Term eine Variable sein kann und dementsprechend auch Var -> Var gilt.
Mich wundert da nur, was uns in der Übung gesagt wurde... naja.

Ist die Übung ausgefallen, oder weiß jemand warum das Blatt zur Übung noch nicht online ist?

Ich frag mich, weil bei dem Übungsblatt so auf die Schreibweise aus der Übung hingewiesen wird.

*nerv* Könnt ihr nicht endlich diesen Thread einmotten?
Der ist von Mai 2007 und handelt davon, ob am 02.05.2007 die Übung stattfindet.

@retr0virus: Erstell doch einfach für jedes Übungsblatt, zu dem du eine Frage hast, einen neuen Thread - so viel mehr Arbeit ist es doch nicht, als Titel "PSÜ, Blatt 123" einzutippen