Sei L die formale Sprache der syntaktisch korrekten Java-Programme?

28.02.2022, 12:52

Könnte mir jemand die Antwort erklären?

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet
Destranix
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
IT, Informatik, Theoretische Informatik
28.02.2022, 13:55

Zu (i):

L ist richtig, denn man kann entscheiden, ob eine Sprache ein syntaktisch korrektes Javaprogramm ist. Somit ist L entscheidbar.
Die leere Menge ist per Definition entscheidbar, insofern ist das auch eine zuläsige Teilmänge.

Zu (ii):

Die Menge der Java-Programme, die für jeder Eingabe halten ist nicht ehtscheidnbar. Siehe dazu das Halteproblem:
Die Menge aller Java-Programme, die zwei Zahlen korrekt addieren ist nicht entscheidbar, da man dazu herausfinden müsste, ob die Addition überhaupt erreicht wird.
Siehe dazu:

code(TM);
int x = a + b;

Wenn man bestimmen würde wollen, ob die Addition stattfindet, dann müsste man zuerst wissen, ob "code(TM)" terminiert/hält. Das geht aber nicht gemäß des Halteproblems.