 |
|||
| HSG |
|
Grammatik für anbncn
- S→aSBC
- S→aBC
- CB→BC
- aB→ab
- bB→bb
- bC→bc
- cC→cc
Prolog-Realisierung nach Dr.Becker, Kaiserslautern
Linke und rechte Seite einer Produktion werden als Listen repräsentiert. Nonterminale Symbole, sogenannte Variablen, werden zur Unterscheidung von Prolog-Variablen durch ein vorangestelltes v gekennzeichnet.
startsymbol([vS]).
produktion([vS],[a,vS,vB,vC]).
produktion([vS],[a,vB,vC]).
produktion([vC,vB],[vB,vC]).
produktion([a,vB],[a,b]).
produktion([b,vB],[b,b]).
produktion([b,vC],[b,c]).
produktion([c,vC],[c,c]).
ableitungsschritt(Wort1,Links,Rechts,Wort2):-produktion(Links,Rechts),
append(Links,Rest,Wort1),
append(Rechts,Rest,Wort2).
ableitungsschritt([K|RWort1],Links,Rechts,[K|RWort2]):-
ableitungsschritt(RWort1,Links,Rechts,RWort2).
ableitungsketteR(Wort2,Wort1,[]):-Wort2=Wort1.
ableitungsketteR(Wort2,Wort1,[regel(Links,Rechts),ZWort|A]):-
ableitungsschritt(ZWort,Links,Rechts,Wort2),
ableitungsketteR(ZWort,Wort1,A).
ableitung(Wort):-startsymbol(S),ableitungsketteR(Wort,S,K),
reverse([Wort|K],A),write(A).
Man beachte, dass eine Ableitungskette im Ableitungsbaum rückwärts gesucht wird. So wird eine mögliche Ableitung sicher gefunden. Das Prädikat ableitungsschritt(Wort1,Links,Rechts,Wort2) liefert im Erfolgsfall in den Variablen Links und Rechts die linke und rechte Seite der benutzten Produktion. Das wird benutzt, um in ableitungsketteR(Wort2,Wort1,[regel(Links,Rechts),ZWort|A]) eine Liste bestehend aus benutzten Regeln und Zwischenworten aufzubauen.
Erläuterungen zu den Prädikaten
Die Anfrage
ableitungsschritt([vC,vB,x,y],L,R,[vB,vC,x,y]).
wird von Prolog mit
L = [vC, vB] R = [vB, vC]
beantwortet. Weitere Lösungen gibt es nicht. Wie kann man das verstehen? Das Wort1 CBxy ist in das Wort2 BCxy überführbar, da CB --> BC eine Produktion ist und xy irgendein Rest. Prolog spaltet über die beiden append-Prädikate aus Wort1 den Teil Links ab und aus Wort2 den Teil Rechts und zwar so, dass der gleiche Rest bleibt. Das bisher Gesagte gilt für das erste Prädikat ableitungsschritt. Es gibt aber noch ein rekursives zweites, das dafür sorgt, dass die aus Wort1 und Wort2 abgespaltene Teile Links und Rechts auch mitten aus den Wörtern stammen dürfen. So sollte abcCBxy in abcBCxy überführbar sein. Ausprobieren! Es fällt auf, dass für die abgespaltenen Teile keine weitere Regel gilt als dass sie jeweils gleich sein müssen.
Eine Ableitung muss aber nicht aus einem Schritt bestehen. Sie könnte auch aus mehreren Schritten bestehen, es entsteht dann eine Ableitungskette. Das Prädikat ableitungsketteR wird wahr, wenn Wort2 aus Wort1 herleitbar ist. Das Prädikat liefert als drittes Argument eine Liste der benutzten Regeln und der Zwischenworte ab. Gilt Wort1 = Wort2, so ist nichts zu tun, das Prädikat ist wahr, die Liste ist leer. Ist Wort2 aus Wort1 herleitbar, so muss es ein Zwischenwort ZWort geben, das direkt vor Wort2 steht (Wort1-->...-->ZWort-->Wort2), dh. ableitung(ZWort,Links,Rechts,Wort2) wird wahr. Nun kann man aus Links und Rechts die Regel regel(Links,Rechts) bilden und Regel und ZWort an die bestehende Ableitungsliste A vorne anhängen. Vom Zwischenwort ZWort versucht man rekursiv zum Wort1 zu kommen.
Möchte man mit ableitung die Ableitbarkeit eines Wortes Wort testen, so wählt man als Wort1 das Startsymbol. reverse dreht die Liste um, write druckt sie aus.
Ableitung von aabbcc
?- ableitung([a,a,b,b,c,c]). [[vS], regel([vS], [a, vS, vB, vC]), [a, vS, vB, vC], regel([vS], [a, vB, vC]), [a, a, vB, vC, vB, vC], regel([vC, vB], [vB, vC]), [a, a, vB, vB, vC, vC], regel([a, vB], [a, b]), [a, a, b, vB, vC, vC], regel([b, vB], [b, b]), [a, a, b, b, vC, vC], regel([b, vC], [b, c]), [a, a, b, b, c, vC], regel([c, vC], [c, c]), [a, a, b, b, c, c]] Yes
Aufgaben
- Bestätige, dass aaabbbccc zur Sprache gehört, abbc dagegen nicht.
Von welchem Typ ist die Sprache?
- In obiger Grammatik sind alle Produktionen im "Wikipedia-Sinn"
(αAβ→αγβ) kontextsensitiv bis
auf die die Produktion CB→BC. Führt man ein Hilfs-Nonterminal H ein, so kann
man die Produktion durch CB→HB, HB→HC, HC→BC ersetzen. Zeige, dass
die Grammatik dann kontextsensitiv ist.
- Die folgende Grammatik erzeugt die gleiche Sprache.
- S→aSBc
- S→abc
- cB→Bc
- bB→bb