0

Hallo zusammen,

 

Ich weiss gar nicht, wie ich das beweisen soll, ob Strings von D entscheidbar sind. Ich weiss, dass ich so etwas mit der Induktion beweisen soll, aber ich weiss nicht einmal wie ich damit beginnen soll. 

 

Entscheidbarkeit bedeutet doch:

Wenn Turing Maschine auf dem w hält und wenn TM das w akzeptiert.

Vielen Dank für euren Hinweis!

Schöne Grüsse

Sayuri

gefragt vor 3 Monaten, 3 Wochen
s
sayuri,
Student, Punkte: 106

 
Kommentar schreiben Diese Frage melden
1 Antwort
1

Es geht ja "nur" um die Frage, ob L(A) endlich ist. Dazu habe ich in

https://www7.in.tum.de/um/courses/theo/ss2017/materials/handout2017.pdf

folgendes gefunden, auf S.88:

Lemma 3.40
Das Endlichkeitsproblem ist für DFAs oder NFAs entscheidbar.

Mit Beweis, aber da bin ich zulange raus. Vielleicht hilft's ja?

 

 

 

geantwortet vor 3 Monaten, 3 Wochen
m
mikn
Lehrer/Professor, Punkte: 8.12K
 

Vielen Dank ich schaus mir einmal an. Leider sehe ich das Bild nicht.   ─   sayuri, vor 3 Monaten, 3 Wochen

Bild von der Seite 88 konnte ich nicht hochladen. Musst du dir aus dem pdf-Dokument raussuchen.   ─   mikn, vor 3 Monaten, 3 Wochen

Kein Problem habs gefunden, vielen Dank! Verstehst du was der genaue Unterschied zwischen Entscheidbar, Nicht-Entscheidbar, Erkennbar und nicht erkennbar ist?   ─   sayuri, vor 3 Monaten, 3 Wochen
Kommentar schreiben Diese Antwort melden