Formale Sprachen und Berechenbarkeit

• Titel: Formale Sprachen und Berechenbarkeit
• Organisation: UNI FRANKFURT
• Seitenzahl: 157

Skript herunterladen (PDF)

Inhalt

• Prof Dr Georg Schnitger Sommersemester
• Kellerautomaten Deterministisch kontextfreie Sprachen Abschlusseigenschaften deterministisch kontextfreier Sprachen
• Path und Query
• Komplexittsklassen und die Chomsky Hierarchie a
• Ziele der Vorlesung
• Begrie und Notationen
•  BEGRIFFE UND NOTATIONEN
• T Y P EN AM E E P RESSION
• c Das Wort w
• KAPITEL ENDLICHE AUTOMATEN
• BACK CODE CODE
• CODE BACK CODE
• BACK CODE CODE
•  MINIMIERUNG ENDLICHER AUTOMATEN
• Minimierung endlicher Automaten
• a a a aa a b b ab
• a a b ab a b
• b a ba b b a bb b
• Q Knoten und hchstens o Q
• w q x w F
• akzeptiert die Sprache L
• a q q q q q q
• b q q q q q q
• Aufgabe Minimiere den folgenden Automaten
• a b c b b b a
• Binrzahl dh Binw a
• wi ni sowie Bin
• n s q q q qn qs
•  Fall v k
•  NICHTDETERMINISTISCHE ENDLICHE AUTOMATEN
• Nichtdeterministische endliche Automaten
• Abschlusseigenschaften und Entscheidungsprobleme
• a b b a b b a a
• Regulre Ausdrucke a
• k Lk Lk Lk pq pq pk Lkk
•  GRAMMATIKEN UND REGULARE GRAMMATIKEN
• Grammatiken und regulre Grammatiken a
• das Startsymbol S V und
• d LG w S w
• ist die von der Grammatik erzeugte Sprache
• n q q qn
• statements statement statement statements assign statement variable expression
• statement assign statement while statement
• while statement while boolean do statements
• KAPITEL KONTE TFREIE SPRACHEN
• Eins Eins Eins S Null Null Null S
• S Eins Eins Eins Eins Eins
• Beispiel Es kann gezeigt werden dass L
• Die ChomskyNormalform und das Wortproblem
•  DIE CHOMSKYNORMALFORM UND DAS WORTPROBLEM
• a b c d a b
• P S a A
• B a S c
• B a C BS Bb C c C
• C a a b b c c
• statt S c c A c S a S
• b
• neu ex bereits
•  DAS PUMPING LEMMA UND OGDENS LEMMA
• Mengen zu bestimmen sind
• Das Pumping Lemma und Ogdens Lemma
• Abschlusseigenschaften kontextfreier Sprachen
• fr A V a und V u
• den Anfangszustand q und
• den anfnglichen Stackinhalt Z sowie a
• Beweis Tripelkonstruktion men A hat die Konguration
• erreicht und hat bisher w w wk gelesen
• Deterministisch kontextfreie Sprachen
• Abschlusseigenschaften deterministisch kontextfreier Sprachen
• ML und regulre a Baumgrammatiken
• KAPITEL ML UND REGULARE BAUMGRAMMATIKEN
• Regulre Baumsprachen a
• Baumsprachen mit eindeutigen Typen
• Modell Alter Rabatt
• modell baujahr rabatt
• Regulre Baumgrammatiken und Baumautomaten a
• Regular Language Description for ML New Generation
•  PATH UND QUERY
• Turingmaschinen und die Churchsche These
• Die Berechnungskraft von Turingmaschinen
•  TURINGMASCHINEN UND DIE CHURCHSCHE THESE
• lschen B links o
• qrucklauf B links
• dem Startzustand DruckeKasten und dem Bandalphabet B
• c c c c
• Die Klasse P
• Berechenbarkeit und Entscheidbarkeit
• Nichtdeterministische probabilistische und Quantenberechnungen
•  und weist damit jedem mglichen Ubergang o
• B ist akzeptierende Berechnung von x
• B fhrt auf C u
• M hlt auf Eingabe w a
• M hlt auf dem leeren Wort a
• Wir setzen T v M
• und haben somit v H T v H
• Aufgabe Es sei L M
• Der Satz von Rice
•  ENTSCHEIDBARE UND REKURSIV AUFZAHLBARE SPRACHEN
• Entscheidbare und rekursiv aufzhlbare Sprachen a
• N akzeptiert w
• Godels Unvollstndigkeitssatz a
• L x ist beweisbar
• und damit ist L rekursiv aufzhlbar Warum a
• L xL x ist beweisbar
• Primitiv rekursive Funktionen
• Beispiele primitiv rekursiver Funktionen und Prdikate a
• Aufgabe Beweise Lemma
• Aufgabe Beweise Lemma und
• x x mod x x
• x xn y
• Sw ySzw x xn y w
• Der beschrnkte Operator a
• Sa Sa Sa pSam m
• x x Induktion nach y y y
• ax x x y x x
• ak M A x m x
• falls x sonst
• ak ak x
• ak M A x ak x
• f x x xn f x
• Der unbeschrnkte Operator a
• Komplexittsklassen und die a Chomsky Hierarchie
• KAPITEL KOMPLE ITATSKLASSEN UND DIE CHOMSKY HIERARCHIE

Vorschau