-
Notifications
You must be signed in to change notification settings - Fork 0
/
P5.pl
53 lines (40 loc) · 2.01 KB
/
P5.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
%Spezifischer PDA L_agb
%Zustandsmenge
%zustand(Z): Z ist Teil der Zustandsmenge
zustand(z).
%Alphabet
%sigma(X): X ist Teil des Alphabets.
sigma(a).
sigma(b).
%Kelleralphabet
%gamma(X): X ist Teil des Kelleralphabets.
gamma(a).
gamma(b).
gamma(s).
%Transitionsrelationen
%delta(AktZ,A,PopS,NeuZ,WriteS): Transition von AktZ zu NeuZ. Zeichen A wird gelesen, PopS wird oben vom Stack entnommen, WriteS wird oben auf den Stack geschrieben.
delta(z,a,a,z,[]).
delta(z,b,b,z,[]).
delta(z,nix,s,z,[]).
delta(z,nix,s,z,[a,s,b]).
%Startzustand
%start(Z): Z ist der Startzustand.
start(z).
%Kellerboden
%floor(A): A ist Kellerbodensymbol
floor(s).
%Allgemeiner Teil
%sigma_stern(Ws): Ws ist ein gültiges Wort über dem Alphabet Sigma.
sigma_stern([]).
sigma_stern([A|Ws]) :- sigma_stern(Ws), sigma(A).
%gamma_stern(Ws): Ws ist ein gültiges Wort über dem Kelleralphabet Gamma.
gamma_stern([]).
gamma_stern([A|Ws]) :- gamma_stern(Ws), gamma(A).
%es(AktZ,AktWs,AktSs,NeuZ,NeuWs,NeuSs): Der Übergang vom Zustand AktZ zu NeuZ, Eingabe AktWs zu NeuWs und dem Keller AktSs zu NeuSs ist ein gültiger Einzelschritt des PDAs.
es(Z, Ws, [G|Ss], Zstrich, Ws, SstrichSs) :- zustand(Z), zustand(Zstrich), sigma_stern(Ws), gamma(G), gamma_stern(Ss), delta(Z,nix,G,Zstrich,Sstrichs),append(Sstrichs,Ss,SstrichSs).
es(Z, [A|Ws], [G|Ss], Zstrich, Ws, SstrichSs) :- zustand(Z), zustand(Zstrich), sigma(A), sigma_stern(Ws), gamma(G), gamma_stern(Ss), delta(Z,A,G,Zstrich,Sstrichs),append(Sstrichs,Ss,SstrichSs).
%es_plus(AktZ,AktWs,AktSs,NeuZ,NeuWs,NeuSs): Der Übergang vom Zustand AktZ zu NeuZ, Eingabe AktWs zu NeuWs und dem Keller AktSs zu NeuSs ist ein gültiger transitiver Abschluss der Einzelschrittrelationen des PDAs.
es_plus(Z,Ws,Ss,Zneu,Wneus,Sneus) :- es(Z,Ws,Ss,Zneu,Wneus,Sneus).
es_plus(Z,Ws,Ss,Zneu,Wneus,Sneus) :- es(Z,Ws,Ss,ZH,WHs,SHs), es_plus(ZH,WHs,SHs,Zneu,Wneus,Sneus).
%lvonM(Ws): Ws ist ein gültiges Wort der Sprache die vom PDA M dargestellt wird.
lvonM(Ws) :- sigma_stern(Ws), start(Z0), floor(S), zustand(Z), es_plus(Z0,Ws,[S],Z,[],[]).