Brauche Hilfe bei Prolog-Aufgabe

[Oliver_G]

Hi,
für den Informatik-Unterricht soll ich über die Ferien etwas in Prolog programmieren, das so einen Vorgang, wie auf dem Bild im Anhang zu erkennen, ablaufen kann.
Ich weiß im Moment nicht genau, wie ich das machen soll, daher versuche ich grad den Ablauf aus dem Anhang nachzuprogrammieren.

Dürfte etwa sowas rauskommen:
startsymbol(start).

produktion(start ['S']).
produktion('S', ['aSTU']).
produktion('S', ['aTU']).
produktion('UT', ['TU']).
produktion('aT', ['ab']).
produktion('bT', ['bb']).
produktion('bU', ['b']).


Allerdings lässt sich das ja aus der Beschreibung ablesen.
Ich weiß nicht weiter :usad: Keine Ahnung wie das gehen soll...

Hat jemand vielleicht nen Prolog-Tutorial in dem man sowas lernt?


PS:
Die Grammatik dafür ist diese hier:
% GRAMMATIK.PL

% einfache Ableitung
einfacheAbleitung(L1, L2):-
L1 = [K|R],
terminal(K),
einfacheAbleitung(R, L3),
L2 = [K|L3].

einfacheAbleitung(L1, L2):-
L1 = [K|R],
variable(K),
produktion(K, L3),
append(L3, R, L2).

% mehrfache Ableitung

% linksrekursiv
ableitungL(A, B):-
einfacheAbleitung(A, B).
ableitungL(A, B):-
ableitungL(A, C),
einfacheAbleitung(C, B).

% linksrekursiv
ableitungLb(A, B):-
ableitungLb(A, C),
einfacheAbleitung(C, B).
ableitungLb(A, B):-
einfacheAbleitung(A, B).

% rechtsrekursiv
ableitungR(A, B):-
einfacheAbleitung(A, B).
ableitungR(A, B):-
einfacheAbleitung(A, C),
ableitungR(C, B).

% rechtsrekursiv
ableitungRb(A, B):-
einfacheAbleitung(A, C),
ableitungRb(C, B).
ableitungRb(A, B):-
einfacheAbleitung(A, B).

% erzeugteSprache einer Grammatik
erzeugteSprache(Wort):-
startsymbol(Start),
ableitungL([Start], Wort),
terminalwort(Wort).

% Prüfroutine für Terminalwörter
terminalwort([]).
terminalwort([Kopf|Rest]):-
terminal(Kopf),
terminalwort(Rest).

% Akzeptor nach der Methode Generieren und Testen
ableitbar(Wort):-
terminalwort(Wort),
startsymbol(Start),
ableitung([Start], Wort).

[del_4901]

Ähm, das habt ihr aber nicht anner Schule, sondern anner Unität?

Ich würde mit der Gramatik erstmal sowas hier bauen:
http://de.wikipedia.org/wiki/LR-Parser

Dann haste einen einfachen Kellerautomaten, da brauchste nur nen Stack für, und ne Handvoll Zustände.


PS: aber mit Prolog und Epilog verbinde ich irgendwie was anderes....

[Oliver_G]

Dochdoch, das machen wir grad in der Schule (Stufe 13).
Ich guck mal. Ggf. mal mit Lehrer in Verbindung setzen (E-Mail) oder nen Kumpel fragen, der auch bei mir im Kurs ist.

Dank & Gruß

[Trap]

Was genau ist die Aufgabe?

[del_4901]

Was genau ist die Aufgabe?
Wenn ich mir den Abl.-Baum da ansehe, denke ich er muss einfach nur einen Automaten bauen, der die Sprache erkennt. Regeln für die CFG stehen ja da, die muss er nur noch Rechts/Links Linearisieren oder in CNF bringen und sich nen Kellerautomaten draus basteln. Anders geht das glaube ich nicht.


PS: für a^n b^n gibbet aber noch ne überschaubare CFL als die die da gegeben ist.

P = { (S-ASB,€), (A-a), (B-b) }

[Oliver_G]

Das weiß keiner ;D
Irgendwie entweder in Delphi (basierend auf nem Automaten, den wir schonmal benutzt haben) oder per Prolog etwas erstellen, was, wie gesagt, Zeichen(-ketten) durch andere Zeichen(-ketten) ersetzt.
Einfach irgendwas, was man vorzeigen kann. :(

Es soll jedenfalls anspruchsvoller als das sein, was ich ihm gezeigt hatte:
% Subjekt -> Name
terminal(X):-
member(X, [julia, tanja, hill, julian, olli, jens]).

% Prädikat -> Verb
terminal(X):-
member(X, [singt, spielt, trommelt]).

% Zusatz
terminal(X):-
member(X, [manchmal, oft, nie, '']).

% Objekt -> Instrument
terminal(X):-
member(X, ['in das Mikrophon', 'Gitarre', 'Bass', 'Schlagzeug']).

variable(X):-
member(X, [satz, subjekt, praedikat, objekt, eigenname, verb, instrument]).

startsymbol(satz).

produktion(satz, [subjekt, praedikat, zusatz, objekt]).

produktion(subjekt, [eigenname]).
produktion(praedikat, [verb]).
produktion(objekt, [instrument]).

produktion(eigenname, ['Julia']).
produktion(eigenname, ['Tanja']).
produktion(eigenname, ['Hill']).
produktion(eigenname, ['Julian']).
produktion(eigenname, ['Olli']).
produktion(eigenname, ['Jens']).

produktion(zusatz, [manchmal]).
produktion(zusatz, [oft]).
produktion(zusatz, [nie]).
produktion(zusatz, []).

produktion(verb, [singt]).
produktion(verb, [spielt]).
produktion(verb, [trommelt]).

produktion(instrument, ['in das Mikrophon']).
produktion(instrument, ['Gitarre']).
produktion(instrument, ['Bass']).
produktion(instrument, ['Schlagzeug']).


Edit: Der Anhang aus dem ersten Post stammt aus meinen Unterlagen. War nur ein Beispiel, das wir ausgeteilt gekriegt hatten während der Schulzeit. (Haben viele Blätter gekriegt ;) )

Gruß

[del_4901]

http://www-ti.informatik.tu-cottbus.de/Skripten/kap2.pdf

S.22 CYK-Algo, der sollte helfen!

http://en.wikipedia.org/wiki/CYK_algorithm

[Trap]

Die Aufgabe könnte auch sein alle möglichen Ableitungsbäume zu erzeugen oder sonst irgendwas.

[HellHorse]

Ich würde mit der Gramatik erstmal sowas hier bauen:
http://de.wikipedia.org/wiki/LR-Parser
...
S.22 CYK-Algo, der sollte helfen!
Gayts noch? Das ist viel zu viel Aufwand! Ich habs so im Gefühl, dass sich die Aufgabe mit minimalem (im schlimmsten Fall 10 LOC) Aufwand lösen lässt. Zumal man Prolog ja einfach das backtracking machen kann (ja, ist ineffizient, aber darum gehts in der Übung nicht).

So wie ich das sehe, müssten die Produktionsregeln als Klauseln definiert werden und das wars dann auch schon fast.

IIRC kommt Prolog sogar einfach eigene Parser definieren.

Verdammt, wenn das nicht alles so lange her wäre :ugly:

[Oliver_G]

So, habe mich jetzt etwas hingesetzt und was gefriemelt:

Hier der Prolog-Quelltext:
-------------------------------------------
terminal(X):-
member(X, [a, b, c]).

variable(X):-
member(X, [S, B, C ,D]).


startsymbol('S').
produktion('S', ['aSbcD']).
produktion('S', ['abC']).
produktion('bC', ['aB']).
produktion('Bb', ['bbC']).
produktion('Bc', ['Bb']).
produktion('C', ['ab']).
produktion('bD', ['aDa']).
produktion('aD', ['aa']).
-------------------------------------------

Hier mein Ableitungsvorgang wie ich mir ihn gedachte habe anhand der Produktionsregeln:
------------------------------------------------------------
S -> aSbcD S -> aSbcD

S -> abC aSbcD -> aabCbcD

bC -> aB aabCbcD -> aaaBbcD

Bb -> bbC aaaBbcD -> aaabbCcD

bC -> aB aaabbCcD -> aaabaBcD

Bc -> Bb aaabaBcD -> aaabaBbD

Bb -> bbC aaabaBbD -> aaababbCD

C -> ab aaababbCD -> aaababbabD

bD -> aDa aaababbabD -> aaababbabaDa

aD -> aa aaababbabaDa -> aaababbabaaa ------------------------------------------------------------

Gefällt meinem Lehrer soweit.

Er schrieb darauf:
"Es können aber wegen der ersten Produktion unendlich viele Worte erzeugt werden.
Was haben die gemeinsam.
Um eine Sprache mit endlich vielen Worten zu beschreiben brauchst Du den Ausdruck (.....)*"

Ich weiß, es liegt an dem S. Und was er mit dem zweiteren meint, weiß ich auch. Muss da irgendwie das leere Wort, also Epsilon, reinbringen, oder? :|
Ich steh grad auf dem Schlauch...


Nochwas:
Wie lässt die entstandene Sprache in einer Formel ausdrücken? "a³ 2(bab) a³", "a³ ba b² ba a³"?

[Gast]

> Er schrieb darauf:
> "Es können aber wegen der ersten Produktion unendlich viele Worte erzeugt
> werden.
> Was haben die gemeinsam.
> Um eine Sprache mit endlich vielen Worten zu beschreiben brauchst Du den
> Ausdruck (.....)*"

Schau dir die Ableitungsregel für das Nichtterminal S an:

S -> aSbcD

Die ist zyklisch, soll heißen, es hält dich niemand davon ab, diese Regel beliebig
oft anzuwenden: S -> aSbcD -> aaSbcDbcD -> aaaSbcDbcDbcd -> ...,
damit können eben prinzipiell beliebig viele Wörter erzeugt werden - jedenfalls unter der Annahme, dass sich 'S' dann jeweils noch vollständig zu Terminalen ableiten lässt.

Wenn du also willst, dass die erste Regel nur einmal angewendet werden kann, dann musst du den Zyklus auflösen, und das geht am einfachsten, indem du die ersten beiden Regeln durch
S -> a[S1]bcD
[S1] -> abC
ersetzt.
(entsprechend dann für genau n Anwendungen der Regel mit Nichtterminalen
[S1], [S2], ..., also z.B.
S -> a[S1]bcD
[S1] -> a[S2]bcD,
[S2] -> abC )

> Nochwas:
> Wie lässt die entstandene Sprache in einer Formel ausdrücken? "a³ 2(bab)
> a³", "a³ ba b² ba a³"?

Allgemein: deine Grammatik ist rein syntaktisch eine kontext sensitive (Typ 1) Grammatik, für welche im Allgemeinen keine solche 'Formel' (ich nehm mal an, du meinst einen regulären Ausdruck) existieren kann, da die regulären Ausdrücke geraden den Typ 3 / regulären Grammtiken/Sprachen entsprechen.

Sollte deine Grammtik allerdings tatsächlich (nach obiger Modifikation - oder auch schon davor, bin zu faul, das auszuprobieren) nur endlich viele Wörter erzeugen, dann ist der einfachste reguläre Ausdruck natürlich, einfach diese endlich vielen Wörter hintereinander zu schreiben - jeweils getrennt durch + (oder | k.A. was ihr dafür benutzt) - sehr hilfreich, ich weiss xD.