rekursive endliche Sprache (Theoretische Informatik, Mathematik :)



  • Kann mir jemand bei der folgenden Aufgabe helfen, verstehe das nicht so richtig:

    Ich soll zeigen, dass jede endliche Sprache L (unechte) Teilmenge von "Summe*" rekursive ist (jede Sprache L mit nur endlich vielen Elementen).
    Gegeben ist, dass die Diagonalsprache D nicht rekursiv ist. Für ein Element n aus den natürlichen Zahlen sei
    Dn := {Element w aus 😨 |w| ≤ n}
    die Diagonalsprache eingeschränkt auf Wörter der Länge maximal n. Ist für jede natürliche Zahl n die Sprache Dn rekursiv? Wieso ist dies kein Widerspruch dazu, dass D nicht rekursiv ist? Was vedeutet die Beobachtung für die praktische Lösbarkeit der Diagonalsprache?

    Würde mich freuen, wenn mir jemand ein Tipp geben könnte, damit ich die Aufgabe lösen kann, danke schon mal!


Log in to reply