100%
def powerset(s): # liefert die Potenzmenge der Menge s
ps = {frozenset()} # Verwendung von frozenset statt set, da Mengen nur
for z in s: # nichtveraenderbare Objekte enthalten duerfen. Beispiel:
ps |= {a | {z} for a in ps} # falsch: a = { {1,2}, {4,5} }
return ps # richtig: a = { frozenset({1,2}), frozenset({4,5}) }
def nea2dea(A): # liefert aequivalenten DEA (Potenzmengenkonstruktion)
[Sigma, Z, delta, z0, F] = A # A ist ein NEA entsprechend Definition 3.12
Z1 = powerset(Z)
delta1 = {} # Ueberfuehrungsfunktion
for S in Z1: # Verwendung von frozenset statt set, da Mengen nur
for a in Sigma: # nichtveraenderbare Objekte enthalten duerfen.
delta1[S,a] = frozenset({s for z in S for s in delta[z, a]})
F1 = {S for S in Z1 if (S & F) != set()}
return [Sigma, Z1, delta1, frozenset({z0}), F1]
def neaKomplement(A): # liefert NEA, der das Komplement von L(A) akzeptiert,
[Sigma, Z, delta, z0, F] = A # wobei A ein NEA entsprechend Definition 3.12 ist
nF = {}
for naz in Z: # durchlaufe alle Zustaende
flag = 0
for az in F: # durchlaufe alle akzeptierenden Zustaende
if (naz == az):
flag = 1 # merke dir, ob der Zustnd naz akzeptierend ist
if (flag==0):
nF.setdefault(naz) # nicht akzeptierenden Zustand in die Menge der akzeptierenden Zustaende aufnehmen
C = [Sigma, Z, delta, z0, nF] # baue komplementaeren NEA C zusammen
return C
def neaVereinigung(A,B): # liefert NEA, der die Vereinigung von L(A) und L(B) akzeptiert,
[ASigma, AZ, Adelta, Az0, AF] = A # wobei A,B NEAs entsprechend Definition 3.12 sind
[BSigma, BZ, Bdelta, Bz0, BF] = B
Sigma = ASigma | BSigma
Cdelta = {}
CZ = set([])
a = 0 # definiere neue Zustaende fuer A
mappinga = {}
for z in AZ:
mappinga[z] = a # Zustaende aus A bekommen gerade Zahlen
CZ.add(a)
a = a + 2
for z in AZ: # Uebertrage Ueberfuehrungen von A nach C
for zeichen in ASigma:
ueberfuehrunga = Adelta[z,zeichen]
Ztemp = {}
for u in ueberfuehrunga:
Ztemp.setdefault(mappinga[u])
Cdelta[mappinga[z], zeichen] = Ztemp
b = 1 # definiere neue Zustaende fuer B
mappingb = {}
for z in BZ:
mappingb[z] = b # Zustaende aus B bekommen ungerade Zahlen
CZ.add(b)
b = b + 2
for z in BZ: # Uebertrage Ueberfuehrungen von A nach C
for zeichen in BSigma:
ueberfuehrungb = Bdelta[z,zeichen]
Ztemp = {}
for u in ueberfuehrungb:
Ztemp.setdefault(mappingb[u])
Cdelta[mappingb[z], zeichen] = Ztemp
Cz0 = a + b # neuen Startzustand fuer C festlegen
CZ.add(Cz0) # und zur Menge der Zustaende hinzufuegen
for zeichen in ASigma: # jedes Zeichen im Anfangszustand Az0 durchlaufen
ueberfuehrunga = Adelta[Az0,zeichen]
Ztemp = {}
for u in ueberfuehrunga:
Ztemp.setdefault(mappinga[u])
Cdelta[Cz0,zeichen] = Ztemp
for zeichen in BSigma: # jedes Zeichen im Anfangszustand Bz0 durchlaufen
ueberfuehrungb = Bdelta[Bz0,zeichen]
Ztemp = {}
for u in ueberfuehrungb:
Ztemp.setdefault(mappingb[u])
Cdelta[Cz0,zeichen] = Ztemp
CF = set([])
for az in AF: # alle akzeptierenden Zustaende von A uebernehmen
CF.add(mappinga[az])
for az in BF: # alle akzeptierenden Zustaende von B uebernehmen
CF.add(mappingb[az])
C = [Sigma, CZ, Cdelta, Cz0, CF]
return C
def neaKonkatenation(A,B): # liefert NEA, der L(A)L(B) akzeptiert,
[ASigma, AZ, Adelta, Az0, AF] = A # wobei A,B NEAs entsprechend Definition 3.12 sind
[BSigma, BZ, Bdelta, Bz0, BF] = B
Sigma = ASigma | BSigma # Alphabete zusammenfuehren
Cdelta = {}
CZ = {}
a = 0 # definiere neue Zustaende fuer A
mappinga = {}
for z in AZ:
mappinga[z] = a # Zustaende aus A bekommen gerade Zahlen
CZ.setdefault(a)
a = a + 2
for z in AZ: # Uebertrage Ueberfuehrungen von A nach C
for zeichen in ASigma:
ueberfuehrunga = Adelta[z,zeichen]
Ztemp = {}
for u in ueberfuehrunga:
Ztemp.setdefault(mappinga[u])
Cdelta[mappinga[z], zeichen] = Ztemp
b = 1 # definiere neue Zustaende fuer B
mappingb = {}
for z in BZ:
mappingb[z] = b # Zustaende aus B bekommen ungerade Zahlen
CZ.setdefault(b)
b = b + 2
for z in BZ: # Uebertrage Ueberfuehrungen von B nach C
for zeichen in BSigma:
ueberfuehrungb = Bdelta[z,zeichen]
Ztemp = {}
for u in ueberfuehrungb:
Ztemp.setdefault(mappingb[u])
Cdelta[mappingb[z], zeichen] = Ztemp
for az in AF: # durchlaufe alle akzeptierenden Zustaende von A
for zeichen in BSigma: # jedes Zeichen im Anfangszustand Bz0 durchlaufen
ueberfuehrungazub = Bdelta[Bz0,zeichen]
Ztemp = {}
for u in ueberfuehrungazub:
Ztemp.setdefault(mappingb[u])
Cdelta[mappinga[az],zeichen] = Ztemp
CF = set([])
for az in BF: # alle akzeptierenden Zustaende von B uebernehmen
CF.add(mappingb[az])
Cz0 = mappinga[Az0] # Startzustand von C ist der von A
C = [Sigma, CZ, Cdelta, Cz0, CF]
return C
def neaDefineK(): # definiert einen NEA K
Sigma = {'1', '2'} # Alphabet
Z = {0, 1, 2} # Zustandsmenge
delta = {} # Ueberfuehrungsfunktion
# Ueberfuehrungsfunktionen S0 - S2 (3 Zustaende)
# Zustand S0
delta[0,'1'] = {1,2}
delta[0,'2'] = {}
# Zustand S1
delta[1,'1'] = {1}
delta[1,'2'] = {2}
# Zustand S2
delta[2,'1'] = {}
delta[2,'2'] = {}
F = {2} # Menge der akzeptierenden Zustaende
A = [Sigma, Z, delta, 0, F] # baue NEA zusammen
return A
def neaDefineL(): # definiert einen NEA L
Sigma = {'1', '2'} # Alphabet
Z = {0, 1, 2} # Zustandsmenge
delta = {} # Ueberfuehrungsfunktion
# Ueberfuehrungsfunktionen S0 - S2 (3 Zustaende)
# Zustand S0
delta[0,'1'] = {1}
delta[0,'2'] = {}
# Zustand S1
delta[1,'1'] = {1}
delta[1,'2'] = {2}
# Zustand S2
delta[2,'1'] = {1}
delta[2,'2'] = {2}
F = {2} # Menge der akzeptierenden Zustaende
A = [Sigma, Z, delta, 0, F] # baue NEA zusammen
return A
def neaErweiterteUEF(delta, z, w): # erweiterte Ueberfuehrungsfunktion eines DEA
for a in w: # durchlaufe jeden einzelne Zeichen a des Wortes w
z = delta[z, a] # suche im Dictionary delta den naechsten Zustand heraus
return z # gebe den letzten Zustand nach Durchlauf des kompletten Wortes zurueck
def neaRun(A, w): # testet, ob der DEA A das Wort w akzeptiert
[Sigma, Z, delta, z0, F] = A # teile DEA in Bestandteile auf
return neaErweiterteUEF(delta, z0, w) in F
def do(wort):
L = neaDefineL()
K = neaDefineK()
#return neaRun(nea2dea(neaKonkatenation(K,L)),wort) # pruefe Zeichenkette mit erzeugtem DEA
return neaRun(nea2dea(neaVereinigung(K,L)),wort) # pruefe Zeichenkette mit erzeugtem DEA
