DEA -> NEA

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

Guten Abend zusammen,

ich bin neu hier und habe auch gleich schon ein Problem (es werden bestimmt noch so einige folgen).
Ich studiere Informatik im zweiten Semester und habe nun dieses WS erstmals mit Python zu tun. Da muss dann natürlich auch ein Forum her :lol:

Ich sitze gerade an einer alten Klausur. Die Aufgabe bei der ich hänge lautet:

"Implementieren Sie eine Python-Funktion dea_to_nea(A), die einen NEA zurückliefert, der die gleiche Sprache akzeptiert wie der DEA A"

"Auf dem Papier" haben wir die Aufgabe so gelöst, dass einfach alle Zustände des DEA als Mengen dargestellt werden. Man zieht geschweifte Klammern um die einzelnen Zustände und hat einen NEA. Der DEA ist ja im Prinzip ein NEA, der den Nichtdeterminismus nicht nutzt.

Aber wie implementiert man das?

Meine Idee war, der Funktion einen NEA zu übergeben und diesen erstmal auszupacken. Dann wollte ich mit einer for-Schleife durch die values laufen und in jedem Durchlauf
val = {val}
ausführen.
Das klappt nicht. Ich denke u.a. weil dictionarys ja nicht veränderbar sind (das kam mir erst hinterher).

Der Lösungshinweis ist übrigens "es sei fast nichts zu tun", also muss es schon ein Kniff sein auf den ich einfach nicht komme.
Und eh ich jetzt Unmengen an Sinnloscode produziere, dachte ich ich frage mal euch :mrgreen:

Für Hinweise und Anregungen wäre ich wirklich dankbar.

Grüße

Severus
Sirius3
User
Beiträge: 18261
Registriert: Sonntag 21. Oktober 2012, 17:20

@Severus: hier weiß niemand, wie Deine Automaten definiert sind, also mit welcher Datenstruktur. Also kann auch niemand etwas dazu zu sagen, wie man das implementiert.

Dictionaries sind nicht nicht-veränderbar.
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

Woher hast du denn, das dictionaries nicht veränderlich waren? Das Gegenteil ist der Fall.

Und Ohne die Definition deines DEA zu sehen, kann man auch nur sagen „tja, geht halt irgendwie“
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

Hallo, und danke erstmal.

Mehr habe ich nicht. Die Aufgabe verlangt, dass ich für einen beliebigen DEA den ich reinwerfe einen NEA zurückbekomme.
Ich habe so ziemlich die komplette Aufgabenstellung abgeschrieben.

Einer unserer DEA aus der Vorlesung wäre zum Beispiel:

def define_dea():

Q={1,2,3,4,5,6,7}
Sigma={"a","b","c"}

delta = {}

delta[0,"a"]=1
delta[0,"b"]=7
delta[0,"c"]=3
delta[1,"a"]=2
delta[1,"b"]=7
delta[1,"c"]=7
delta[2,"a"]=1
delta[2,"b"]=7
delta[2,"c"]=3
delta[3,"a"]=4
delta[3,"b"]=7
delta[3,"c"]=7
delta[4,"a"]=7
delta[4,"b"]=7
delta[4,"c"]=5
delta[5,"a"]=6
delta[5,"b"]=7
delta[5,"c"]=7
delta[6,"c"]=5
delta[6,"a"]=7
delta[6,"b"]=7
delta[7,"a"]=7
delta[7,"b"]=7
delta[7,"c"]=7

F={0,6}

A=[Q,Sigma, delta, 0,F]

return A

def delta_dach_dea(delta, q,w):
for i in w:
q=delta[q,i]
return q

def run_dea(A,w):
[Q,Sigma,delta, q0,F]=A
return delta_dach_dea(delta,q0,w) in F

Für den müsste das z.B. funktionieren
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

Ich sehe gerade, es hat die Formatierung etwas zerhackt. Ich hoffe ihr könnt trotzdem sehen worum es geht...
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

Na dann - welche Teil ist denn genau unterschiedlich beim NEA gegenüber dem DEA?
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

Nachtrag: und so funktioniert der Code bestimmt nicht. Dein Delta ist falsch definiert. Da musst du nochmal nachbessern.
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

Na der NEA kann in mehreren Zuständen gleichzeitig sein, die Werte von delta sind daher Mengen.

Eigentlich müsste ich "nur" für jeden key das value in eine Menge packen, oder?

- was passt am delta nicht?
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

ich Muss mich korrigieren, gehen tut das.

Code: Alles auswählen

>>> d = {}
>>> d[10, 'a'] = 100
>>> d
{(10, 'a'): 100}
Insofern vergiss den Hinweis.

Was dein Problem angeht: genau, die Werte sind Mengen. Und wie baust du eine Menge mit einem Element?
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

Zum Beispiel mit a ={1}

Dann hab ich die Menge a mit dem einen Element 1

Darum habe ich versucht:

Code: Alles auswählen

def dea_to_nea(A):

[Q,Sigma;delta,q0,F]=A

for val in delta.values():
    val = {val}
return A 

-mit mäßigem Erfolg

DA hänge ich fest
Sirius3
User
Beiträge: 18261
Registriert: Sonntag 21. Oktober 2012, 17:20

@Severus: das erste, was Du bekommst ist ein SyntaxError, weil das kein gültiges Python ist. Dann solltest Du auch keine Datenstrukturen zu verändern versuchen, was zum Glück so nicht geht, sondern neue erzeugen.
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

Also sollte ich eher versuchen ein komplett neues delta zu erzeugen?
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

Ja. Zb mit einer dict-comprehension, oder schoen altmodisch zu fuss.
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

"schön altmodisch zu Fuss"

- genau das 8)

Wie stelle ich das jetzt an?

Kann man die Schlüssel eines bestehenden dictionarys einzeln abrufen um sie mit den ebenfalls einzeln abgerufenen Werten in ein neues dict zu packen? (Nur das die Werte dann jetzt in Mengen abgelegt werden)
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

Natuerlich kann man das. Dazu empfiehlt sich der Blick ein Grundlagen-Tutorial. Oder in die Dokumentation. 'Du wirst ueberrascht sein davon, was du siehst!'
Severus
User
Beiträge: 13
Registriert: Freitag 5. Januar 2018, 16:49

Hallo zusammen,

habe das Problem jetzt mit

Code: Alles auswählen

def dea_to_nea(A):
    [Q,Sigma,delta,q0,F]=A
     
    for k,v in delta.items():
        delta[k]={v}

gelöst. Scheint zu funktionieren. Danke Euch 8)
Antworten