% Grammatik Beispiel: a^nb^nc^n
% kontextsensitive Grammatik
% Version: JUL 2016

terminal(a).
terminal(b).
terminal(c).

variable('S').
variable('B').
variable('C').

startsymbol('S').

produktion(['S'], [a, 'S', 'B', 'C']).
produktion(['S'], [a, 'B', 'C']).
produktion(['C', 'B'], ['B', 'C']).      % Ordnung beibehalten
% kontextsensitive Produktionen
produktion([a, 'B'], [a, b]).
produktion([b, 'B'], [b, b]).
produktion([b, 'C'], [b, c]).
produktion([c, 'C'], [c, c]).

% Entscheidung des Wortproblems
% für kontextsensitive Grammatiken

einfacheableitung(A, B, N):-
  % kontextsensitive Produktionen
  produktion(P, Q),
  aufteilenliste(P, A, L, R),
  append(Q, R, QR),
  append(L, QR, B),
  length(B, M),
  M =< N.        % laengenmonoton
  
ableitung(A, B, N):-
  einfacheableitung(A, B, N).
  
ableitung(A, B, N):-
  ableitung(A, C, N),
  einfacheableitung(C, B, N).

wortproblem(Wort):-
  terminalwort(Wort),
  startsymbol(Start),
  length(Wort, N),
  ableitung([Start], Wort, N).
  
erzeugteSprache(X):-
  startsymbol(Start),
  ableitung([Start], X, 100),
  terminalwort(X).

terminalwort([]).
terminalwort([Kopf|Rest]):-
  terminal(Kopf),
  terminalwort(Rest).

% Hilfsprädikate
    
/* aufteilenliste(+Teilliste, +Liste, -Links, -Rechts) 
   Teilt eine Liste an der Teilliste in zwei Listen auf.
   Liefert in Links die Liste der vor bzw. in Rechts die 
   Liste der auf Teiliste folgenden Listenelemente.
*/   

aufteilenliste(Teilliste, Liste, [], Rechts):-
  append(Teilliste, Rechts, Liste).
aufteilenliste(Teilliste, [Kopf|Rest], [Kopf|Links], Rechts):-
  aufteilenliste(Teilliste, Rest, Links, Rechts).