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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 1 Minuspunkt
107 Aufrufe

Mit dem Risiko, dass sowas schon mal gefragt wurde.

 

Bei einem nicht deterministischen KA, zum Beispiel bei einem Palindrom, wo der KA die Mitte richtig "abschätzen" muss. Bei langen Wörtern ist es sehr unwahrscheinlich, dass der Keller richtig "schätzt". Bedeutet das, dass der Keller also meistens das Wort nicht akzeptieren würde und man deshalb den Automaten sehr oft mit dem Wort durchgehen müsste bis er zumindest einmal erkannt wird. Und wenn es ja einmal akzeptiert wird von mehreren Versuchen reicht es ja? Ist das so richtig?

 

Was aber wenn ich nun ein Palindrom mit Milliarden Stellen habe, lasse den KA ein paar Millionen mal laufen und es wurde immer falsch geschätzt und das Wort wurde durch das falsche "schätzen" kein mal erkannt. Dann geht man fälschlicherweise davon aus, dass das Wort nicht korrekt ist, obwohl es das aber doch ist, richtig?

 

in KEL-AF von utdbu utdbu Tutor(in) (107k Punkte)  
erneut getaggt von utdbu utdbu

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Woher kommen denn diese (nicht ganz korrekten) Formulierungen? Ein KA kann nicht schätzen.

Bei einem nichtdet. KA sprechen wir davon, dass er "raten" kann - das ist allerdings etwas salopp formuliert und bedeutet nicht schätzen! Ein nichtdet. Automat (also sowohl KA als auch EA, TM, ...) kann beliebig viele Konfigurationen auf einmal betrachten, weil er ja aus einem Zustand in beliebig viele Folgezustände übergehen kann. Er kann also in n Berechnungsschritten alle nach n Schritten erreichbaren Konfigurationen betrachten. Das bedeutet, dass er aus den viele möglichen Konfigurationsfolgen, die vom Startzustand aus existieren, die richtige (also die, die zu einer akzeptierenden Konfiguration führt) aussuchen kann. In diesem Sinn kann er "raten" - er rät aber immer richtig, solange es eine akzeptierende Konfigurationsfolge gibt. Auf diese Weise kann ein nichtdet. KA diejenige Konfigurationenfolge erraten, die gerade die Mitte eines potentiellen Palindorms trifft (und zwar für Palindrome beliebiger Länge!). (Es ist natürlich zu beachten, das Nichtdeterminismus ein mathematisches Konstrukt ist - so einen ratenden Automaten können wir in Wirklichkeit nicht bauen; in der Wirklichkeit sind wir immer deterministisch.)

Ein det. KA kann die Mitte eines Palindorms nicht finden und auch nicht "abschätzen".

Viele Grüße

Lukas König
von utdbu utdbu Tutor(in) (107k Punkte)  
...