Automaten und Sprachen

Prädikate sind Aussagen über mathematische Objekte, die wahr oder falsch sein können. “Funktionen” mit booleschen Rückgabewerten: . Siehe DMI .

Normalformen (allgemein, kanonische Formen) helfen, das Vergleichsproblem zu lösen (ob zwei Aussagen dieselben sind).

Nicht für alle = Es gibt einen Fall, für den nicht

Grundmenge , Prädikat . Konstruierte Menge

Term	Definition
Vereinigung
Schnittmenge
Komplement
Differenz

-Tupel:

Eine Folge von logischen Schlüssen, die zeigen, dass die Aussage aus den gegebenen Voraussetzungen folgt.

Beweistechnik	Anwendungsfall
Konstruktiver Beweis	Liefert explizite “Lösung” / Algorithmus
Widerspruchsbeweis	Geeignet für Unmöglichkeitsaussagen. Z.B.
Vollständige Induktion	Für Aussagen, die für alle gelten.

Term	Definition
Alphabet	Eine nichtleere endliche menge heisst Alphabet. Die Elemente von heissen Zeichen.
Wort	Eine Zeichenkette der Länge ist ein -Tupel in . Ein Element von heisst Wort der Länge . Wörter haben immer endliche Länge.
Leeres Wort	Die Zeichenkette der Länge heisst das leere Wort.
Menge aller Wörter	Leeres Wort ist immer drin
Abgekürzte Schreibweisen von Wörtern
Sprache	Teilmenge

Term	Definition
Länge des Wortes	, ist Länge des Wortes
Anzahl Zeichen	Sei . Dann ist die Anzahl Zeichen im Wort

Definition	Tabellenform	Zustandsdiagramm von
Zustände: Alphabet: Übergangsfunktion: Startzustand: Akzeptierzustände:

Wichtig: Ein Pfeil für jedes Zeichen in jedem Zustand für validen DEA

Übergänge ausghend von für Zeichen nacheinander anwenden.

Der DEA akzeptiert das Wort , wenn er von Startzustand in einen Akzeptierzustand überführt.

Gegeben ein DEA . Die von akzeptierte Sprache ist

Die Sprache heisst regulär, wenn es einen DEA gibt mit

Für ein Wort setze Insbesondere

Gegeben: reguläre Sprache über . Rekonstruiere mit:

Gleicher Zustand gleiches

Ziel: Nicht unterscheidbare Zustände zusammenlegen

Vorgehen:

1. Akzeptierzustand Nichtakzeptierzustand
2. Iteration: alle unterscheidbaren Paare suchen
3. Verbleibende Paare sind ununterscheidbar zusammenlegen

Ist eine reguläre Sprache, dann gibt es , die pumping length so, dass jedes Wort mit in drei Teile zerlegt werden kann mit:
Oder: genügend lange Wörter () einer regulären Sprache () können alle in einem Anfangsstück der Länge N () aufgepumpt werden ().

Was zeichnet reguläre Sprachen aus?

• Reguläre Ausdrücke
• Lange Wörter: * kommt im regulären Ausdruck vor
• Blöcke mit * können beliebig oft wiederholt werden
• Wörter können “aufgepumpt” werden

Behauptung: Die Sprache ist nicht regulär.

Beweis (Widerspruch):

1. Annahme: ist regulär

2. Gemäss Pumping Lemma gibt es die Pumping Length

   • Es darf keine Annahme über die konkrete Grösse von gemacht werden!

3. Wähle ein Wort mit

   • Die Definition muss verwenden!

4. Aufteilung des Wortes gemäss Pumping Lemma

5. Auswirkung des Pumpens

   • für mindestens ein (mit Begründung!)
6. Widerspruch und Schlussfolgerung, dass die Annahme nicht zutreffen kann

Definition	Akzeptieren
Endliche Menge von Zuständen: Alphabet: Übergangsfunktion: Startzustand: Akzeptierzustände:	Ein NEA akzeptiert das Wort , wenn es eine Wahl von Übergängen gibt, derart, dass das Wort den Automaten in einen Akzeptierzustand überführt. Faustregeln Nur genau diejenigen Pfeile einzeichnen, die man zum Akzeptieren braucht. Erlaube Alternativen

a-Übergang von aus nicht eindeutig Welchen Übergang soll man nehmen? Beide Möglichkeiten probieren und akzeptieren, falls eine der Möglichkeiten auf einen Akzeptierzustand führt. Zufallsgenerator (probabilistischer endlicher automat, PEA)

Zustand = Menge der möglichen Zustände Akzeptieren = Ob NEA im Zustand sein könnte

Gegeben eines NEA. Übergangsfunktion für Mengen

Satz	Implementation
Ein NEA kann in einen DEA umgewandelt werden mit wie oben definiert	Thompson-NEA: Zustand realisiert durch Markierung der Zustände in realisiert durch Verschieben von Markierungen Akzeptieren: mindestens ein Akzeptierzustand markiert

Term	Definition
-Übergang	Kann ohne Verarbeitung eines Zeichens genommen werden.
	NEA mit -Übergängen

Einen kann man immer in einen NEA umwandeln. Beweis: Menge der von aus mit -Übergängen erreichbaren Zustände ersetzen durch

Lassen reguläre Sprachen regulär sein.

Produktautomat:

Schnittmenge	Vereinigungsmenge
Differenzmenge	Symmetrische Differenz

Operationen verändern nur Endzustände:

Term	Definition
Schnittmenge
Vereinigung
Differenz

WICHTIG: -Übergänge immer hinzufügen

die Klasse der regulären Sprachen ist abgeschlossen unter regulären Operationen

Formeln, die Zeichenketten beschreiben.

1. Buchstaben stehen für sich selbst, mit Ausnahme der Metazeichen (escape character)
2. Verkettung: Zeichen und Formeln hintereinanderschreiben
3. = ein beliebiges Zeichen,
4. : Alternative, = a oder A
5. : Wiederholung, beliebige viele
6. : Gruppierung
7. Zeichenklassen: , = alles ausser a, b, oder c

Erweiterungen / Dialekte

1. : zwischen un Wiederholungen
2. : mindestens eines,
3. : optional,
4. Symbole für Zeichenklassen: Ziffern, whitespace, ,

Term	Definition
Regulärer Ausdruck	Zeichenkette zur Beschreibung einer regulären Sprache
Reguläre Operationen
Verallgemeinerter NEA	, dessen Übergänge mit regulären Ausdrücken beschriftet sind
Primitive reguläre Ausdrücke	Reguläre Ausdrücke für Wörter mit Länge

zu jedem regulären Ausdruck gibt es einen DEA

Keine Übergänge nach und nur ein Akzeptierzustand

Reduktion

Regulärer Ausdruck

Nach Entfernen aller Zwischenzustände bleibt ein regulärer Ausdruch von

jede reguläre Sprache lässt sich mit einem regulären Ausdruck beschreiben

Interessantes projekt (DEA Lexer DSL): Ragel

Messung	Folgerung
Für Regulären Ausdruck erzeugen Laufzeit für Akzeptieren von durch messen	Laufzeit : NEA-Implementation Laufzeit : DEA-Implementation

Term	Definition
CFL	Context Free Language
CFG	Context Free Grammar
PDA	Pushdown Automata

Kontextfreie Grammatik: : Variablen : Terminalsymbole (Alphabet) : Regeln der Form mit : Startvariable Ableitung und erzeugte Sprache Regel erzeugt aus das Wort aus ableiten: oder von erzeugte kontextfreie Sprache Erzeugte Sprache Die Menge der Wörter, die von einer kontextfreien Grammatik aus der Startvariablen abgeleitet werden können, wird mit bezeichnet und heißt die von erzeugte Sprache. Kontextfreie Sprache Eine Sprache heißt kontextfrei, wenn es eine kontextfreie Grammatik gibt, die die Sprache erzeugt.

Parse Tree mit der Grammatik

Es ist nicht garantiert, dass es für die Ableitung eines Wortes nur einen einzigen Syntaxbaum gibt. Man sagt, die Grammatik ist nicht eindeutig, wenn sie mehrere Syntaxbäume für die gleichen Wörter erlaubt.

Die Klasse der kontextfreien Sprachen ist abgeschlossen unter regulären Operationen.

Reguläre Sprachen sind kontextfrei.

Seien und kontextfreie Sprachen mit Grammatiken . Wir nehmen an, dass die Variablen- und Regelmengen disjunkt sind, also . Zudem sei eine Variable, die nicht in enthalten ist. Dann gilt:

Alternative ist kontextfrei mit der Grammatik

Verkettung ist kontextfrei mit der Grammatik

*-Operation ist kontextfrei mit der Grammatik

Es spielt keine Rolle, in welchem Kontext das Zeichen vorkommt, die Regel kann immer angewendet werden

Je nach Kontext kann eine Regel nicht unbedingt angewendet werden

Eine CFG ist in Chomsky-Normalform, wenn auf der rechten Seite nicht vorkommt und jede Regel von der Form oder ist, zusätzlich ist die Regel erlaubt.

1. Neue Startvariable (wenn nötig)
2. -Regeln: kann weggelassen werden
3. Unit-Rules: aus kann man wie aus auch machen
4. Verkettungen: ersetzen durch und falls ein Terminalsymbol ist: .

1. Ableitung eines Wortes ist immer in Regelanwendungen möglich. Beweis:

   • Regeln der Form um aus ein Wort aus Variablen zu erzeugen
   • Regeln der Form um das Wort zu erzeugen
   • insgesamt Regelanwendungen
2. Deterministischer Parse-Algorithmus mit Laufzeit

Gegeben

1. Grammatik G =
2. Variable
3. Wort

Frage

Ist ableitbar? Formell geschrieben:

• Spezialfall (Epsilonregel, )
• Spezialfall (Terminalsymbolregel)

• Fall

Ideen Parse Tree aus und Variablen in Tabelle füllen Prinzip Einem Teilwort entspricht ein Feld der Tabelle (rot hinterlegt) Das Feld wird mit den Variablen gefüllt, aus denen das Teilwort abgeleitet werden kann. Beispiel Parsen des Wortes ()[()]()[()] Definitionen Die Felder und heissen korrespondierende Felder im Ableitungsdreieck des Feldes .

Spezifikation der Regeln in maschinen-lesbarer Form:

• Variablen: <variablen-name><variablen-name>
• Einzelne Zeichen: AA
• Zeichenketten: 'BEISPIEL''BEISPIEL'
• Regeln: <variablen-name> ::= Ausdruck<variablen-name> ::= Ausdruck
• Ausdrücke sind Folgen von Variablen, einzelnen Zeichen oder Zeichenketten, getrennt durch ||

Definition	Achtung!
Literale in Anführungszeichen oder Apostroph == statt ::=::= Variablen ohne << und >>, dürfen Leerzeichen enthalten Komma für Verkettung ,, Regel-Endzeichen ;; Kommentare (* ... *)(* ... *) Optionale Wiederholung {...}{...} Option [...][...] Gruppierung (...)(...) Ausnahme: --	Keine Operatorpriorisierung Zweideutig! Keine eindeutige Evaluation!

Expression-Term-Factor-Grammatik verwendet Links-Rekursion korrekte Auswertung von links nach rechts. Parsetree wertet aber Ausdrücke von rechts nach links aus! Alternative Expression-Term-Factor definition mit Rechtsrekursion statt Linksrekursion:

Unendlich grosser Speicher

• Immer nur das oberste Element sichtbar
• Beliebig tief

Kann Sprachen akzeptieren, die nicht regulär sind, ist aber nicht deterministisch. Beachte: möglich

Definition Stackautomat : Zustände : Eingabe-Alphabet : Stack-Alphabet : : Startzustand : Akzeptierzustände

Übergänge vom Input vom Stack entfernen (Bedingung) auf den Stack

Ist eine kontextfreie Sprache, dann gibt es einen Stackautomaten , der akzeptiert, .

Grundgerüst

Regel	Regel	Regel

Variablen

Wörter beschreiben Pfade durch den Automaten: Variable Wörter, die von nach führen mit leerem Stack

Regeln

Regeln beschreiben, wie sich Wege zerlegen lassen: Wege von nach können verstanden werden als Wege von nach und von dort nach

1. Nur ein Akzeptierzustand: Neuen Akzeptierzustand und Übergänge von allen vorherigen Endzuständen zu erstellen.

2. Stack leeren: Mit einem Element erweitern, sodass garantiert werden kann, dass der Stack am schluss leer ist.

3. Jeder Übergang legt entweder ein Zeichen auf den Stack oder entfernt eines

Ausgangspunkt: standardisierter PDA mit Startzustand und .

1. Startvariable:

2. Regeln:

Pumping Lemma für CFL

Ist eine CFL, dann gibt es eine Zahl , die Pumping Length, derart, dass jedes Wort mit zerlegt werden kann in fünf Teile derart, dass

Mit dem Pumping Lemma kann man beweisen, dass eine Sprache nicht kontextfrei ist.

Grammatik in CNF

Wiederverwendete Variable

gross genug Variablen werden im Parse Tree wiederverwendet Die “unterste” wiederverwendete Variable erzeugt zwei Wörter:

Pumpen

anstelle des “untersten” verwenden

Term	Definition
Endlich	Eine Menge heisst endlich, wenn jede Injektion auch eine Bijektion ist
Abzählbar unendlich	Eine Menge heisst abzählbar unendlich, wenn es eine Bijektion gibt, also . Bsp: , Menge aller DEAs/NEAs/PDAs/CFGs
Überabzählbar unendlich	Eine Menge heisst überabzählbar unendlich, wenn sie nicht abzählbar unendlich ist. Bsp: , Menge aller Sprachen
Gleich mächtig	Mengen und heissen gleich mächtig, , wenn es eine Bijektion gibt
Unendlich	Eine Menge heisst unendlich, wenn sie gleich mächtig wie eine Teilmenge ist

abzählbar unendlich, :

1. abzählbar unendlich
2. abzählbar unendlich
3. Abzählbar unendlich:
4. überabzählbar unendlich
5. überabzählbar unendlich

Merhere Stacks (Speicherzellen) = RAM (Band).

Jeder DEA oder NEA kann damit emuliert werden.

1. Der Speicher ist unbegrenzt
2. In jeder Zelle genau ein Zeichen
3. Es ist immer nur eine Speicherzelle einsehbar
4. Der Inhalt der aktuellen Zelle kann beliebig verändert werden
5. Bewegung immer nur eine Zelle nach links oder rechts
6. Kein weiterer Speicher (nur die Zustände eines endlichen Automaten und das eine Zeichen)

Term	Definition
Record	Speichereinheit fester grösse
Bandalphabet	Alphabet , welches aus Speicherzellen (Stacks) besteht
Schreib-/Lesekopf	Aktuelle Schreib-/Leseposition

Definition	Zustandsdiagramm
(deterministische) Turing-Maschine : Zustände : Alphabet : Bandalphabet, : : Startzustand : Akzeptierzustand : Ablehnzustand,
	Übergänge
	Übergang möglich, wenn unter dem Schreib- / Lese-Kopf Aktuelles Feld auf dem Band wird mit überschrieben Kopfbewegung: links, rechts

Programmablauf

• Input-Wort auf Band
• Schreib- / Lesekopf positioniert auf 1. Zeichen
• Maschine starten, Einzelschritte ausführen
• Maschine hält in oder : Wort akzeptiert / Verworfen

Laufzeit:

Vorher	Nachher

Der Gang der Berechnung mit einer TM kann dokumentiert werden, indem der Bandinhalt nach jedem einzelnen Verarbeitungsschritt protokolliert wird.

Links	Rechts

Übergangsfunktion Bei jedem Übergang maximal verschiedene Möglichkeiten: Mehrere mögliche Berechnungswege Wort akzeptieren wenn es einen Berechnungsweg gibt, der zu führt. (auch wenn es Wege gibt, die auf führen!) Simulationsidee Alle Berechnungswege durchführen, maximal

Simulation auf Standard-TM Verwende 3 Bänder: Arbeitsband Kopie von w Liste aller Folgen von Wahlmöglichkeiten Simulation Kopiere w von Band 2 auf Band 1 Führe TM aus auf Band 1 mit Wahlmöglichkeiten von Band 3 Inkrementiere zur nächsten Folge von Wahlmöglichkeiten auf Band 3 Laufzeit:

Simulierbar in

Jedes andere Alphabet als kann binär codiert werden.

Simulierbar in Zeit

Simulierbar in Zeit

Um eine Mehrbandmaschine mit Bändern auf einer einfacheren Maschine zu simulieren, kann die unabhängige Bewegung der Schreib-/Leseköpfe mithilfe eines -spurigen Bandes (Daten + Zeiger für Schreib-/Lesekopf) nachgebildet werden.

Simulierbar in Zeit

Die AVR-Mikrokontroller-Familie von Atmel verwendet intern drei unabhängige Datenpfade:

• Flash-Speicher, der den Programmcode enthält
• Statisches RAM, welches zur Laufzeit veränderliche Daten speichert
• Peripheriegeräte.

Die von Neumann-Architektur vereinheitlicht Daten- und Programmspeicher.

Beidseitig unendliches Band kann durch ein Alphabet doppelter Wortbreite realisiert werden, somit äquivalent.

Eine TM erkennt das Wort , wenn die Maschine auf dem Input im Zustand anhält.

Sind und Turing-erkennbare Sprachen, dann sind auch der Durchschnitt und die Vereinigungsmenge Turing-erkennbar.

Es gibt überabzählbare viele Sprachen , die nicht Turing-erkennbar sind.

Aufzähler

TM mit einem Drucker, mit dem Wörter ausgedruckt werden können.

ist rekursiv aufzählbar wenn es einen Aufzähler gibt, der alle Wörter aufzählen kann. ist dann auch Turing-erkennbar.

Deterministisch

Eine TM heisst Entscheider, wenn sie auf jedem Input anhält.

Nichtdeterministisch

Eine nichtdeterministische TM heisst Entscheider, wenn jede Berechnungsgeschichte terminiert.

Turing-erkennbare Sprache

heisst Turing-erkennbar, wenn es eine TM gibt mit .

Turing-entscheidbare Sprache

heisst Turing-entscheibar, wenn es einen Entscheider gibt mit .