HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material/Prolog

Grammatik für anbncn

  1. S→aSBC
  2. S→aBC
  3. CB→BC
  4. aB→ab
  5. bB→bb
  6. bC→bc
  7. 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.
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
  1. Bestätige, dass aaabbbccc zur Sprache gehört, abbc dagegen nicht. Von welchem Typ ist die Sprache?

  2. 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.

  3. Die folgende Grammatik erzeugt die gleiche Sprache.
    1. S→aSBc
    2. S→abc
    3. cB→Bc
    4. bB→bb
    Untersuche diese Aussage mit einem Prolog-Programm.