Lernziel 7 Was sind Ableitungsbäume kontextfreier Grammatiken? Wie wir aus dem Beitrag zu KE5 bereits wissen, sind reguläre Sprachen (Typ-3, rechte Seite einer Regel besteht nur aus einem Terminal, dem ein Nonterminal folgt oder einem leeren Wort) eine echte Teilmenge der kontextfreien Sprachen (Typ-2, linke Seite der Regel besteht nur aus einem Nonterminal). Die Typ-3-Sprachen sind nur noch […]

Update 3: Korrektur der Beweisidee für Durchschnitt, nicht Vereinigung. Danke Phil. Update 2: Korrektur Aufgabe aus Lernziel 3. Danke Mike. Update: Aufgabe mit Lösung hinzugefügt um aus einem Automaten eine Regelmenge abzuleiten. Ohne viele Worte: weiter in KE6. Lernziel 3 Wie konstruiert man zu einem endlichen Automaten einen regulären Ausdruck mit ? Hier kommt einiges […]

Vorletzte Kurseinheit. Und dazu noch ein eig. sehr schönes Thema. Die letzte KE und diese hier gehören ganz eng zusammen; ich kämpfe noch mit mir nicht einen einzigen Eintrag aus beiden Kurseinheiten zu gießen. Ich empfehle euch beide in einem Tab/Fenster aufzumachen damit Ihr beide Einträge vor der Nase habt und zwischen ihnen blättern könnt […]

Update 2: Markus hat eine Ungenauigkeit im Lernziel 8 gefunden. Ist korrigiert, Danke. Update: Beispiel für die regulären Ausdrücke, sowie Gleichungen für die Funktion aus Lernziel 5 hinzugefügt. Ebenfalls Antworten zu allen Lernzielen verfasst. Noch drei Kurseinheiten, dann ist TIB auch schon vorbei. In dieser Kurseinheit geht es um Grammatiken. Häufig wird in der Literatur zunächst die […]

Lernziel 3 Wie ist der Vollständigkeitsbeweis zu ? steht für das englische satisfiability. Also ein Erfüllbarkeitsproblem. Es wird gefragt ob eine aussagenlogische Formel erfüllbar ist (erinnert ihr euch an KNF/DNF aus der technischen Informatik? Das hier ist nicht weit weg...). Da eine Formel nur endlich viele variablen enthält, die nur mit und belegt werden können, haben wir […]