Update: Einwand von Felix aufgenommen. Update: Marion hat einen Fehler bei der Berechnung der gefunden. Danke! Update: Eine Registermaschine kann nicht die Subtraktion, sondern nur die arithmetische Differenz. Update: Hinweis darauf, dass das erste Register bei der Eingabecodierung für eine Maschine belegt werden kann (wir haben keine Einschränkungen), aber nicht durch die Eingabecodierung für eine Registermaschine! […]

Update: Fehler im Automaten behoben. Letzter Beitrag zum Thema... ich tippe besonders langsam, versprochen 😉 Lernziel 5 Was sind determinierte Kellerautomaten? Wir könnten zwar mit nichtdeterministischen Kellerautomaten leben und würden es sogar. Aber es gibt da ein Problem: wir können sie technisch nicht realisieren. Den determinierten Kellerautomaten hatten wir im vorherigen Beitrag auch bereits definiert. Uns […]

Update 2: Einzel- und Mehrschrittrelationen, sowie Überführungsfunktion genauer erklärt. Großes Update: Fehlerbeseitigung und langes Beispiel zum Beweisverfahren Sprache zu Automat(en) zu Grammatik zu Sprache (Lernziel 4). Lernziel 3 Wie sind Kellerautomaten und die von ihnen akzeptierte Sprache definiert? Noch einmal zur Auffrischung: alle Sprachen, die ein endlicher Automat akzeptiert sind regulär. Haben wir aber eine […]

Ich wollte das zwar in einen meiner Beiträge verwursteln, aber ich bin gerade derart begeistert, dass ich das unbedingt loswerden muss. Vor ein paar Stunden bin ich über ein Programm gestolpert. Es kann natürlich sein, dass die halbe Welt das schon kennt und ich mich hier als Unwissender zum Affen mache, aber das Risiko gehe […]

Update: Flüchtigkeitsfehler rausgenommen. Das ist nun die letzte Kurseinheit der theoretischen Informatik B. Traurig? 😉 In dieser Kurseinheit geht es um kontextfreie Sprachen (also Sprachen, die Typ-2 und -3 erzeugen). Am besten man betrachtet die letzten drei Kurseinheiten gemeinsam, ggf. erstelle ich eine kleine Zusammenfassung der Kernaussagen bei Gelegenheit um aus den Puzzleteilen wenigstens teilweise […]