Prove that given a DFA D, the problem of checking whether the number of strings accepted by D is finite is decidable.

Aufrufe: 804     Aktiv: 01.08.2020 um 21:33
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

Diese Frage melden
gefragt

Student, Punkte: 205

 
Kommentar schreiben
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?

 

 

 

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 38.86K

 
Vielen Dank ich schaus mir einmal an. Leider sehe ich das Bild nicht.   ─   sayuri 01.08.2020 um 20:26
Kein Problem habs gefunden, vielen Dank! Verstehst du was der genaue Unterschied zwischen Entscheidbar, Nicht-Entscheidbar, Erkennbar und nicht erkennbar ist?   ─   sayuri 01.08.2020 um 21:33

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.