Prüfungsprotokoll

Frage

Antwort

Definition der Berechenbarkeit? Was ist alles berechenbar?

Ist die Funktion f(x)=3x berechenbar?

Kurze Skizze des Flußdiagramms genügte

Definition Wort-berechenbar

Funktionen sind wort-berechenbar, wenn man eine Band-Maschine oder eine Keller-Maschine angeben kann, die die Funktion berechnet.

Zusammenhang Register-berechenbar und Keller-berechenbar

Diagramm zu fn = ng erläutern

Wann heißt eine Zahlenmenge rekursiv?

A rekursiv, wenn A := f^-1{0}, f Î R⁽¹⁾

Ist die Menge M = {y | y = 2^x } rekursiv?

Ist M auch rekursiv-aufzählbar?

Idee für ein Flußdiagramm einer verallgemeinerten Register-Maschine

Ist die Menge M := { x³ | x Î N } rekursiv?

Welche Eigenschaften der Funktion fließen dabei ein?

Ja.

Monotonie und Berechenbarkeit

Wann ist eine Zahlenmenge rekursiv aufzählbar?

A rekursiv aufzählbar, wenn A := Def(f), f Î P⁽¹⁾

Ist die Menge der Kubikzahlen rekursiv?

Ja, denn man kann eine Registermaschine angeben, die testet, ob eine Eingabezahl eine Kubikzahl ist. Liegt eine Kubikzahl vor, so wird eine 0, sonst eine 1 ausgegeben.

Wie sieht die Registermaschine aus, die die Menge der Kubikzahlen entscheidet?

In einer Schleife werden jeweils die Kubikzahlen von 1³ bis n³ gebildet, wobei n³ die erste Zahl größer oder gleich der Eingabezahl ist. Ist die berechnete Zahl gleich der Eingabezahl, so wird eine 0 ausgegeben, sonst 1. Das Berechnungsverfahren terminiert in jedem Fall.

Ist die Menge der Kubikzahlen rekursiv aufzählbar?

Da die Menge entscheidbar ist, ist sie auch rekursiv aufzählbar.

Wie muß die Registermaschine (für rekursive Kubikzahlen) modifiziert werden, damit die Menge der Kubikzahlen rekursiv aufzählbar wird?

Dazu muß nur die Abfragebedingung von größer gleich auf gleich geändert werden. Liegt eine Kubikzahl vor, so wird 0 ausgegeben und die Maschine hält. Liegt keine Kubikzahl vor, entsteht eine Endlosschleife. Somit liegen nur die Kubikzahlen im Definitionsbereich der Funktion, die durch die Registermaschine definiert wird.

Was bedeutet Numerierung?

Beispiele

Berechenbarkeit von Zahlenfunktionen

1) berechenbar, wenn man eine m-rekursive Funktion angeben kann, die den Funktionswert berechnet

2) wenn es Registermaschine M gibt mit f_M=f

Operator der primitiven Rekursivität aufschreiben

Prk(g,h)(x) := f ist so definiert, daß f(x,0) := g(x) und Prk(x,y+1) := h(x,y,f(x,y)). Dabei müssen die Funktionen g und h m-rekursiv sein.

m-Rekursivität mündlich definieren, m-Operator aufschreiben, m-Berechenbarkeit

Warum muß "(i<n) (x,i)ÎDef(h) gelten?

Funktion heißt m-rekursiv, wenn sie durch endliches Anwenden der Operatoren (Sub, Prk und m) auf die Grundmenge GR entsteht

Wie lautet die math, Definition für f^-1{0}?

{x Î Def(f) | f(x) = 0 }

Kann man m-rekursive Funktionen auch mit Hilfe der Registermaschinen berechnen?

Ja, da die primitiv-rekursiven Grundfunktionen register-berechenbar sind, und man die Operatoren Sub, Prk und m durch verallgemeinerte Register-Maschinen berechnen kann. Verallgemeinerte Register-Maschinen deshalb, damit man alle register-berechenbaren Funktionen beim Flußdiagramm verwenden kann.

Beweis für Äquivalenz zwischen Register- und m-Berechenbarkeit

Genau die Codierung der Menge Konfigurationen angeben

Þ Verschlüsselung der Konfigurationen (t: N ® KON); Angabe der Funktion "es: N ® N"; Angabe der Schrittzahlfunktion SZ (hier, und nur hier wird der m-Operator gebraucht); Folgerung zur Gesamtschrittfunktion, AA, AC etc.

Ü Vor allem ist wichtig zu wissen, daß durch die drei Operatoren aus berechenbaren Funktionen wieder berechenbare Funktionen entstehen

---

Zunächst wird eine Standardnumerierung für die Konfigurationen KON der Register-Maschine eingeführt, wobei die Zustände q mit Nummern bezeichnet werden. Die Register-Maschine zur Berechnung einer Funktion verwende nun m Register. Die Numerierung n: N ® (q,d) = N x N^m ordnet jeder Zahl eine Konfiguration zu. Nun können die Funktionen zur Bestimmung der Semantik einer Register-Maschine ES, SZ, GS durch m-rekursive Funktionen nachgebildet werden, wobei statt auf Konfigurationen mit den entsprechenden Nummern der Konfigurationen gerechnet wird. Zur Bestimmung der Schrittzahl wird der m-Operator verwendet.

Was gilt bei rekursiven Funktionen?

Die Schrittzahlfunktion muß auch rekursiv sein, d.h., ohne den m-Operator auskommen. Das ist erfüllt, wenn es eine Obergrenze für die Schrittzahlfunktion in Abhängigkeit von der Eingabe gibt, also $c Î N SZ(q₀,EC(n)) £ cn+c

Zusammenhang register-berechenbar zu keller-berechenbar für n=1 erläutern

Berechenbarkeit von Wortfunktionen

Bandmaschine mit genauer Datenmenge und Eingabecodierung hinschreiben: Man sollte sich ein Datenelement genau aufschreiben und sich überlegen, welches einzelne Zeichen unter dem Kopf, welches rechts und links davon steht, d.h., nicht das leere Wort, sondern ein Blank

Erläuterung der Arbeitsweise einer Bandmaschine

Hilfssymbollemma

Zu jeder Bandmaschine M über (S, G, B) gibt es eine Bandmaschine M' über (S, G', B) mit F_M=F_M' und G'=S È {B}

Beweisidee: Verschlüsselung von G durch W_n({A,B}) mit AÎS, 2ⁿ ³ #G

(Hinweis: wird im Kurs benötigt für die Definition der Standardnumerierung j_i; Angabe der Simulationsrelation genügte und Hinweis auf Eingabe- und Ausgabecodierung incl. Eingabe- und Ausgabeanpassung)

Zusammenhang zwischen Berechenbarkeit Zahlen/Wortfunktionen

bijektive Abbildung

Satz registerberechenbare Funktionen Û wortberechenbare Funktionen

Standardnumerierung n : N ® W(S) (ist bijektiv)

Anschauliche Erklärung der Bedeutung des Satzes

Definition rekursive bzw. rekursiv-aufzählbare Mengen

Was ist mit Durchschnitt, Komplement, Vereinigung etc.

Ist die leere Menge rekursiv?

Ja, z.B. die konstante Funktion f(n) = x (x <> 0) erfüllt die Bedingung

Ist die Menge der geraden Zahlen rekursiv?

Ja! Es gibt totale rekursive Funktion mit f(i)=0 Û i gerade. Flußdiagramm einer entsprechenden RM

n-rekursive/aufzählbare Mengen, Definition, Abgeschlossenheit

Selbstanwendbarkeitsproblem

Definition und Beweis exakt aufgeschrieben

Arbeitsweise einer Registermaschine

Definition der Datenmenge einer Registermaschine

Der Datenbereich D ist eine unendliche Folge von natürlichen Zahlen, also D := N^N

Wie ist die Semantik einer Register-Maschine definiert?

Zunächst kann man jeden Zustand der Register-Maschine in einer Konfiguration KON darstellen, wobei KON ein Tupel (q,d) ist, mit q Î Q und d Î D. Durch das Flußdiagramm der Register-Maschine wird eine Einzelschrittfunktion ES definiert, die als Funktion KON ® KON dargestellt werden kann. Beginnend von der Startkonfiguration werden solange rekursiv Einzelschritte durchgeführt, bis ein Endzustand oder eine Konfiguration außerhalb des Definitionsbereichs von ES erreicht wird. Wird ein Endzustand erreicht, so ist damit die Schrittzahlfunktion SZ und die Gesamtschrittfunktion GS definiert. Den berechneten Funktionswert erhält man aus der Endkonfiguration.

Ist die Funktion f(x) := div berechenbar?

Wann ist eine Funktion m-rekursiv?

m-rekursive Funktionen sind durch primitiv-rekursive Grundfunktionen (Null- und Einstellige Nullfunktion, Nachfolgerfunktion), den Projektionsfunktionen und den drei Operatoren Sub, Prk und m definiert. Durch die Operatoren können aus den Grundfunktionen weitere m-rekursive Funktionen definiert werden. Diese neu entstandenen Funktionen können wiederum zur Definition von anderen Funktionen mittels der erwähnten Operatoren verwendet werden.

Wie ist eine Bandmaschine anschaulich definiert?

Arbeitsweise einer Bandmaschine

Definition der Datenmenge einer Bandmaschine

Unterschied Bandalphabet G zu Eingabealphabet S, Beziehung der Alphabete zueinander

Definition der Eingabecodierung einer Bandmaschine

Bedeutung von n (=Standardnumerierung von Wortfunktiionen)

genaue Definition war nicht verlangt

Definition n-rekursiver Mengen

Zusammenhang von rekursiven und rekursiv-aufzählbaren Mengen

Gilt auch die Umkehrung?

rekursiv Þ rekursiv-aufzählbar

Wie ist die weitere Definition für rekursiv-aufzählbar?

eine totale Funktion g mit Bild(g) =A

Ist die Vereinigung rekursiv-aufzählbarer Teilmengen auch rekurisv-aufzählbar?

Was ist mit der Vereinigung leerer Mengen?

Idee: mit geraden und ungeraden Zahlen beide Teilmengen aufzählen

Wie sind Numerierungen allgemein definiert?

Formulieren des utm-Theorems

"u_j Î P⁽²⁾ mit u_j(i,x) := j_i(x). Somit ist also j_i(x) partiell rekursiv.

Wann ist eine Funktion f: N^k ® N berechenbar?

Definition Register-berechenbar, m-rekursiv

Ist die Funktion f: N ® N mit ("i) f(i) := div brechenbar?

Wie zeigen Sie das?

Ja

Register-Maschine angeben, die für keine Eingabe hält

Zeigen Sie die Äquivalenz von Register-Berechenbarkeit und m-Rekursivität

Wie zeigt man die andere Richtung?

Sei zunächst f: N^k ® N m-rekursiv. Dann entsteht f in endlich vielen Schritten durch Anwenden der Operatoren Sub, Prk und m auf die sogenannten "primitiv-rekursiven Grundfunktionen". Zunächst zeigt man, daß letztere Register-berechenbar sind. Danach zeigt man, daß die Operatoren Sub, Prk und m berechenbare Funktionen in berechenbare Funktionen überführen

Indem man die in der Flußdiagramm-Semantik als m-rekursiv nachweist

Was ist ein wichtiges Ergebnis des Beweises "m-rekursiv Û Register-berechenbar" bzgl. primitiv-rekursiver Funktionen

Rechenzeitsatz für primitiv-rekursive Funktionen

Eingabecodierung, Datenmenge von Band-Maschinen

Definitionen im Kurs

Welche Verbindung besteht zwischen beiden Berechenbarkeitsbegriffen?

betrachte Funktionen g: N^k ® N, f:W(S)^k ® W(S). Dann gilt:

g Register-berechenbar Þnogon^-1 Keller-bb

f Keller-berechenbar Þn^-1 ogon Register-bb

Was kann über das Verhältnis der register- und wort-berechenbaren Funktionen ausgesagt werden?

Über eine Standardnumerierung des Wortbereichs W(S) können die register- und wort-berechenbaren Funktionen ineinander umgerechnet werden. Also mit n_S : N ® W(S) ergibt sich: Ist g register-berechenbar, so ist f := n_Sgn_S^-1 wort-berechenbar. Ist f wort-berechenbar, so ist g := n_S^-1fn_S register-berechenbar. Die Berechenbarkeitsbegriffe stimmen also überein.

Definieren Sie einen Berechenbarkeitsbegriff für abzählbare Mengen

Was bedeutet es, wenn eine Menge n-rekursiv ist?

Definition rekursive, rekursiv aufzählbare Menge

Ist die Menge M = { y | y = 2^x } rekursiv?

Idee für ein Flußdiagramm einer verallgemeinerten Register-Maschine

Gibt es noch andere Charakterisierungen rekursiv aufzählbarer Mengen?

Eine Menge A ist rekursiv-aufzählbar Û A = Bild(f) für ein f Î R⁽¹⁾

Wie steht es mit der leeren Menge. Ist die r.a.? Wie zeigt man das?

Ja. Definiere f: N ® N mit ("i) f(i) := div; dann ist Def(f) = Æ

Ist die Vereinigung zweier beweisbarer Mengen wieder beweisbar?

Wann heißt eine Menge A Í N entscheidbar?

Ist {n³ | n Î N} entscheidbar?

$f Î R⁽¹⁾.A = f^-1(0)

Ja. Verbale Angabe eines Flußdiagramms

Unterschied zwischen Entscheidbarkeit und Beweisbarkeit

Unterschied der beiden Begrifffe; Nennung einer rekursiv aufzählbaren Menge, die nicht entscheidbar ist, samt Diagonalbeweis

Zusammenhang zwischen entscheidbar und beweisbar

A ist entscheidbar Û A ist rekursiv aufzählbar und `A ist rekursiv aufzählbar.

Wann heißt eine Menge A Í N beweisbar?

Gilt A,B beweisbar Þ A È B, bzw. A Ç B beweisbar? Beweisidee?

$f Î P⁽¹⁾.A = Def(f)

Es gilt beides. Beweisidee: $f,g Î P⁽¹⁾. A = Def(f), B=Def(g) Þ f+g berechenbar und Def(f+g) = A Ç B. Für A È B ähnlich: Allerdings muß es zwei Maschinen geben, die f bzw. g berechnen und deren Programme "parallel" in einer neu zu schaffenden Maschine abgearbeitet werden müssen, die genau dann hält, wenn die Maschine für f oder g hält.

Ist `A beweisbar, wenn A beweisbar ist?

Ja, wenn A entscheidbar ist!

Sei A rekursiv. Ist dann das Komplement `A auch rekursiv?

mit Beweis

Wann ist eine Menge A Í N rekursiv aufzählbar?

Ist die Funktion f(x)=div berechenbar?

Ja. Register-Maschine angeben

Wie zeigt man m-rekursiv Û Register-berechenbar?

Þ Zu zeigen ist, daß jede m-rekursive Funktion Register-berechenbar ist. In Satz 3.2.2 wurde bewiesen, daß jede Funktion aus GR Register-berechenbar ist. Damit ist jede Funktion f, die in endlich vielen Schritten aus GR entsteht (also f Î PRK) wiederum Register-berechenbar, denn die Operatoren Sub, Prk und sie m transformieren berechenbare Funktionen in wiederum berechenbare Funktionen

Ü Es sei f : Nk ® N Register-berechenbar. Dann gibt es eine Register-Maschine M=(F,N^k,N,EC^k,AC) mit einem Endzustand, so daß f_M=f. Die in der Semantik-Definition auftretenden Funktionen lassen sich (im wesentlichen) mittels Substitution aus GR erzeugen. Dazu wird jede Konfiguration durch eine Nummer codiert. Wenn man dann auf Nummern von Konfigurationen rechnet, sind EC’s, AC’s und Schrittzahlfunktionen primitiv-rekursiv und die Schrittzahlfunktion sowie die Gesamtschrittfunktion sind m-rekursiv. Daraus ergibt sich die m-Rekursivität von f.

Wie werden die Konfigurationen codiert?

Mit Hilfe der Cantorschen Tupelfunktion

Was sind Konfigurationen?

KON := Q ´ D (Zustandsmenge kreuz Datenmenge)

Wie ist Prk definiert?

Seien k Î N, g:N^k ® N und h:N^k-2 ® N. Dann sei Prk(g,h) := f:N^k+1 ® N die durch folgende Gleichungen eindeutig bestimmte Funktion

f(x,0) := g(x)

f(x,y+1) := h(x,y,f(x,y)) für alle x Î N

Was sind primitiv-rekursive Grundfunktionen?

Nullstellige Nullfunktion, einstellige Nullfunktion, Nachfolgerfunktion, i-te k-stellige Projektion

Was sind berechenbare Wortfunktionen?

Funktionen über einem Alphabet, die sich mit einer Band- oder Kellermaschine berechnen lassen.

Was ist eine Bandmaschine?

Kurze verbale Erläuterung

Welche Befehle gibt es für Bandmaschinen?

Kopf um eine Position nach rechts,

Kopf um eine Position nach links,

Schreiben eines Zeichens a Î G,

Testen, ob sich das Zeichen a Î G auf der Bandstelle unter dem Kopf befindet.

Was ist die Datenmenge der Flußdiagramme von Bandmaschinen?

Die Datenmenge D des Flußdiagramms F einer Bandmaschine ist definiert durch d := { d:Z ® G | d(z) ¹ B nur für endlich viele z Î Z} Metasprachliche Bezeichnung: [d(-i)d(-i+1)...d(-1)d(0)d(1)...d(j), wenn d(z)=B für alle z mit z < -i und z > j

Wie ist die Eingabecodierung bei Bandmaschinen definiert?

EC^(k):(W(S))^k ® D definiert durch EC^(k) (w₁,w₂,...w_k) := [e,B,w₁Bw₂B...w_k]

Welchen Inhalt haben bei [e,B,w₁Bw₂B...w_k] die Bandstellen d(-1), d(0) und d(1)?

B, B und das erste Zeichen von w₁.

Was ist eine Numerierung?

Eine Numerierung einer Menge M ist eine surjektive Abbildung n : N ® M

Wann heißt eine Menge A Í N rekursiv?

A heißt entscheidbar oder rekursiv, Û es eine total-rekursive Funktion f : N ® N (d.h. f Î R⁽¹⁾ gibt mit A = f^-1{0}

Ist die leere Menge rekursiv?

Ja. Passende Funktion: R0 := R0+1; HALT

Wann heißt eine Menge A Í N rekursiv-aufzählbar?

A heißt beweisbar oder rekursiv-aufzählbar, Û es eine Funktion f : N ® N (d.h. f Î P⁽¹⁾) gibt mit A = Def(f)

A ¹ Æ heißt beweisbar oder rekursiv-aufzählbar, Û es eine Funktion g : N ® N (d.h. g Î R⁽¹⁾) gibt mit A = Bild(g)

Ist M := {p| p=2ⁿ, n Í N } rekursiv-aufzählbar?

Ja, M ist sogar entscheidbar. Nach verbaler Definition einer solchen Entscheidungsfunktion, mußte die Funktion so geändert werden, daß sie beweist, aber nicht entscheidet (Lösung: Befehl R0 := R0+1 durch Endlosschleife ersetzen

Wie ist die Beweisbarkeit von Mengen definiert?

Sei k ³ 1, A Í N^k. A heißt rekursiv aufzählbar oder beweisbar, Û es eine berechenbare Funktion f : N^k ® N (d.h. f Î P^(k)) gibt mit A = Def(f)

Wie ist die n-Rekursivität von Mengen definiert?

Es sei n : N ® M eine Numerierung. Sei X Í M eine Teilmenge von M. X heißt n-rekursiv, Û es ein f Î P⁽¹⁾ gibt, so daß für alle i Î Def(n) der Wert f(i) existiert und f(i) = 0 Û n(i) Î X

Wie ist die n-Beweisbarkeit von Mengen definiert?

Sei n : N ® M eine Numerierung. Sei X Í M eine Teilmenge von M. X heißt n-beweisbar, Û es ein f Î P⁽¹⁾ gibt, so daß für alle i Î Def(n) der Wert f(i) existiert und f(i) existiert Û n(i) Î X

Welcher Zusammenhang besteht zwischen Entscheidbarkeit und Beweisbarkeit?

A Í N Þ A und N \ A beweisbar

Gibt es eine Menge, die beweisbar, aber nicht entscheidbar ist?

Wie ist K_j definiert?

Was bedeutet hierbei das j?

Ja, die Menge K_j

K_j = {i Î N | j_i(i) existiert }

Das ist die Standardnumerierung aller berechenbarer Funktionen f:N®N

Gibt es rekursiv-aufzählbare, aber nicht rekursive Mengen?

Ja, z.B. die Menge K_j := {i|i Î Def(j_i)}

Kurze Erläuterung von j_i

Diese Funktion ist die Standardnumerierung der partiell rekursiven Funktionen R⁽¹⁾

Warum ist K_j rekursiv aufzählbar?

Da die Funktion j_i(i) über eine universelle Funktion u_j(i,i) laut dem utm-Theorem berechnet werden kann. Diese universelle Funktion ist dabei partiell rekursiv.

Gibt es eine Menge, die beweisbar, aber nicht entscheidbar ist?

Ja, K_j

Beispiel für eine nicht rekursiv-aufzählbare Menge

Definition von K_j mit exaktem Beweis

Hierbei reichte es nicht aus nur zu sagen, daß die im Beweis vorkommende Funktion g nicht berechenbar ist, das mußte formal bewiesen werden

Wie ist K_j definiert?

K_j Í N ist definiert durch K_j := {i| i Î Def(j_i)}

Zeigen Sie entweder daß K_j nicht entscheidbar oder daß `K_j nicht beweisbar ist?

Beweis von K_j nicht entscheidbar durch Diagonalisierung:

Sei g : N ® N, die sich von jeder Funktion j_i an der Stelle i unterscheidet. g(i) := div, falls j_i(i) existiert, 0 sonst, d.h. g ÏP⁽¹⁾. Wäre K_j rekursiv, gäbe es eine Funktion f ÎR⁽¹⁾ mit f^-1{0} = K_j . Dann gilt g(i) := div, falls f(i)=0, 0 sonst. Da nach Annahme f Î R⁽¹⁾ gilt, ist g berechenbar. Widerspruch!

Beweis von `K_j ist nicht rekursiv-aufzählbar durch Diagonalisierung:

Sei RA := {Def(j_i)| iÎN} die Menge aller rekursiv-aufzählbaren Teilmengen von N. Die Menge `K<sub>j</sub> ist diagonalisierbar über RA. Für jedes i Î N gilt nämlich: i Î `K_j Û i Ï Def(j_i), woraus folgt, `K<sub>j</sub> ¹ Def(j<sub>i</sub>). Damit ist `K_j nicht rekursiv-aufzählbar.

Wie transformiert man einen nichtdeterministischen Automaten in einen äquivalenten deterministischen Automaten?

Zusammenhang zwischen regulären Ausdrücken und endlichen Automaten

Beweis ausgeführt. Formeln für die a^k_ij

Wie kann man einen determinierten endlichen Automaten in einen regulären Ausdruck umwandeln?

Erläutern des Konstruktionsbeweises: endlicher Automat ® regulärer Ausdruck

E(i,j,k) näher erläutern

Was sind reguläre Mengen?

Wie sind reguläre Sprachen definiert?

3 Klassifizierungen angeben:

Zusammensetzung aus Æ, {a}, È, × und *

Rechtslineare Grammatik

Rechtslineare Normalformgrammatik

rechtslineare Chomsky-Grammatiken

Endlicher (nicht) determinierter Automat

Reguläre Ausdrücke ...

Auf welche Art werden Worte der regulären Sprache erzeugt?

Wenn man eine rechtslineare Grammatik zugrunde legt, so werden Worte der Sprache dadurch erzeugt, daß beginnend vom Startsymbol der Grammatik solange über die Ableitungsregeln der Grammatik abgeleitet wird, bis das entstandene Wort nur noch Terminalsymbole enthält. Alle ableitbaren Terminal-Worte zusammen bilden dann die erzeugte reguläre Sprache.

Wie sind rechtslineare Grammatiken definiert?

Eine Grammatik G=(S,P,R,S) heißt rechtslinear, wenn alle Regeln die Form A ® wB oder A ® w haben mit w ÎW(S), A,B Î P

genaue Erklärung der Alphabete P und S

Wie sind rechtslineare Normalform-Grammatiken definiert? Wie sieht die Regelmenge für eine rechtslineare Grammatik aus?

Eine Grammatik G=(S,P,R,S) ist in rechtslinearer Normalform, wenn alle Regeln die Form A ® aB oder A ® e haben mit a ÎW(S), A,B Î P

Wie überführt man rechtslineare Grammatiken in rechtslineare Normalform?

1. Normieren der Terminalregeln (aus A ® a wird A ® aC und C ® e)
2. Normieren der Regellänge (aus A ® abB wird A ® aA₁ und A₁ ® bB
3. Eliminieren von (längentreuen) Regeln der Form A ® B

Was ist die Chomsky-Normalform?

kontextfreie Sprachen

Definition, Darstellungsformen, Pumpinglemma (nur verbal, keine schriftlichen Details)

Was ist eine kontextsensitive Grammatik?

Was ist eine e-freie Grammatik und wie erstellt man sie?

Abgrenzen von nichtdeterministisch und deterministisch kontext-freien Sprachen

Kann die Menge aller Zahlen, die eine natürliche Zahl als Teiler haben deterministisch erkannt werden? Die Zahlen sollen dabei durch geeignetes Alphabet z.B. S = {'0', '1',... '9'} verschlüsselt werden.

Kann diese Menge auch nichtdeterministisch erkannt werden? Wie sieht es hier mit der Laufzeit aus?

Ja. Turingmaschine beschreiben, die das kann und Laufzeitverhalten sehr grob abgeschätzt

Ja. Laufzeit wird erheblich geringer.

Ist die Sprache L = { w | w Î W({a,b}, #_a(w) ³ 2} regulär?

Wie sieht eine Grammatik aus, die L erzeugt?

Kann die Grammatik auch Worte erzeugen, die nicht in L liegen?

Ja, denn man kann eine rechtslineare Grammatik angeben, die alle Worte der Sprache erzeugt.

Die Grammatik G = ({a,b},P, R, S) besitzt folgende Regelmenge R: R = {S ® bS|aA, A ® bA|aB, B ® bB|aB|e}

Während der Ableitung entstehen Worte mit Nichtterminalzeichen, die nicht in L liegen. Wenn Worte allerdings nur aus Terminalzeichen bestehen, so liegen alle diese Worte in L

Wie sind die kontextfreien Sprachen charakterisiert?

Gibt es noch andere Charakterisierungen?

Wie müßte dieser Kellerautomat arbeiten?

Sie werden von kontextfreien Grammatiken erzeugt.

Sie werden von Kellerautomaten erkannt.

Ist die Sprache L := { a^m bⁿ | m £ n } regulär?

Zeigen Sie, daß L nicht regulär ist?

Ist L kontextfrei?

Nein. Pumping-Lemma

Ist die Sprache L := { aⁿ bⁿ c^m | 2m = n } regulär?

L := { aⁿ b a^m | n < m }

nicht regulär, aber kontextfrei

Wäre L regulär, gäbe es einen determinierten Automaten mit k Zuständen der L akzeptiert

Untersucht wird das Verhalten des Automaten bei Eingabe von a^kba^k. Es werden 3 Fälle unterschieden, in denen je zwei gleiche Zustände bei Verarbeitung unterschiedlicher Teilstücke des Eingabewortes auftreten.

Sei L={a^mbⁿ}. Ist L regulär?

Nein, läßt sich mit dem Pumping-Lemma beweisen.

Wie lautet das Pumping-Lemma für reguläre Mengen?

Sei L Í W(S) regulär. Dann gilt: $ p mit "w Î L (|w| ³ p Þ $ x,y,z Î W(S) xyz=w Ù 1£|y|£p Ù "i ³ 0 xyⁱz Î L