Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

prüfen ob eine Überführungsfunktion richtig ist

+1 Punkt
50 Aufrufe
Kann ich mit XWizard überprüfen, ob meine Überführungsfunktion richtig ist?
 

Gibt es eine andere Möglichkeit diese auf vollständige Korrektheit zu prüfen?
​Durch ein Testwort wird es ja noch nicht allgemein gezeigt...
Gefragt 5, Jan 2018 in KEL-AA von Anonym  

Eine Antwort

0 Punkte

Ich bin nicht sicher, ob ich ganz richtig verstehe, was Sie wissen möchten.

Sie haben recht, ein Testwort zeigt nur für den einen Fall, dass die Überführungsfunktion in diesem Fall korrekt ist; es kann keine Aussage über ihre Korrektheit im Allgemeinen abgeleitet werden (außer, wenn sie nicht korrekt ist - dann reicht u.U. ein einziger Testfall).

Durch Testen kann man nie vollständig sicher sein, dass die Überführungsfunktion korrekt ist.

Leider gibt es allerdings für alle Automatentypen ab det. Kellerautomaten kein automatisches Beweisverfahren, um zu zeigen, dass die Semantik der Überführungsfunktion korrekt ist (die Semantik ist "das, was das Programm tut"). Sie kennen das ja vom Programmieren in Java etc. Wenn man sicher sein will, dass ein Programm korrekt ist, muss man sich schon hinsetzen und das in jedem Einzelfall von Hand beweisen.

(Es gibt Model-Checking-Verfahren, die einen halbautomatischen Mittelweg darstellen, aber damit haben wir uns nicht beschäftigt.)

Kurz gesagt, können Sie also leider nicht mit dem XWizard überprüfen, ob eine Überführungsfunktion korrekt ist. Und auch sonst gibt es kein automatisches Werkzeug, das das kann. Für die Klausur müssen Sie trotzdem in der Lage sein, korrekte Überführungsfunktionen anzugeben - und diese Korrektheit eventuell beispielhaft an einem Testwort zu demonstrieren.

(Beweisen, dass eine Überführungsfunktion korrekt ist, müssen Sie dagegen normalerweise nicht.)

Beantwortet 6, Jan 2018 von Lukas König Dozent (10,065,100 Punkte)  
...