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

1 Pluspunkt 0 Minuspunkte
184 Aufrufe

Hallo,

muss ich bei den ersten beiden Übergängen in den Zustand s1 wechseln?

Könnte nicht in s0 bleiben?

Dazu würde ich die Übergänge s1 zunächst alle in s0 umbenennen.

Danke im Voraus

 

in 2011-B-02 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

in diesem Fall muss man in den Zustand s1 wechseln, da das leere Wort Teil der Sprache ist und anderenfalls dein Automat nicht deterministisch wäre! (Denn dann dürfte s0 kein Endzustand sein und du bäruchtest einen lambda Übergang der Form (s0,lambda,k0), womit dein Automat nicht mehr deterministisch ist!)

Gruß,

Adam (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Aber wenn man doch den "(s0,lambda,k0)" Fall hat, dann ist der Automat doch deterministisch?

Denn dann kann man doch auch in s0 aufhören, wenn kein Wort eingegeben wird, oder?

Wann ist denn ein Automat genau deterministisch & wann nicht?

Bin gerade etwas verwirrt.
0 0
Hallo,

Ein KA ist nicht deterministisch, wenn es zwei Übergänge gibt, die der Automat zur selben Zeit ausführen könnte. Einfaches Beispiel:

(s0,a,k0)->(s0,ak0)

(s0,a,k0)->(s0,bk0)

Lese ich also am anfang ein a, dann erfülle ich die Voraussetzung für beide Übergänge und weiss nicht, welche ich ausführen soll (d.h. die Definition der Erkennung bei ndet. KA: Wenn es eine Folge von Überführungen gibt, sodass es akzeptiert wird, dann ist es Teil der Sprache).

Schauen wir uns jetzt speziell das mit dem lambda übergang an. Wir hätten also

(s0,lambda,k0)->(se,k0)

(s0,a,k0)->(s0,ak0).

Dies ist beides ausführbar, wenn mein Wort mit einem a beginnt! Denn das lambda dort heißt nicht, dass dieser Übergang verwendet werden darf, wenn kein Buchstabe gelesen wird, also das Band leer ist. Ein lambda Übergang darf immer gemacht werden, wenn Zustand und Kellerzeichen übereinstimmen.

Würde also ein a gelesen werden, dürfte ich trotzdem einen lambda-Übergang machen! Und genau so geht der Determinismus verloren und deshalb muss auch der Anfagnszustand ein Endzustand sein, wenn das leere Wort Teil der Sprache ist. Denn die einzige Alternative ist der lambda Übergang, den haben wir aber gerade augeschlossen.
Gruß, Adam (Tutor)
Darf ich in den Keller was anderes schreiben, als ich lese?
...