185.691 Einführung in die Theorie der Informatik VO

Folien zur Vorlesung: http://www.logic.at/lvas/eti/

1998-03-17

1998-03-24

1998-03-31

1998-04-21

1998-05-05

Reguläre Mengen: Alle Sprachen, die aus einem Alphabet durch Vereinigung, Verkettung und Kleene-Stern gebildet werden können.

Algebraische Notation

s statt {s} für s e S

EBNF-Notation

z.B.

real = digit {digit} "." {digit} [scale]

scale = "E" ["+"|"-"] digit {digit}

Reguläre Definitionen

Verwendung von Abkürzungen für reguläre Teilausdrücke, erhöht nicht die Ausdruckskraft.

Bessere Strukturierung, bessere Lesbarkeit.

Keine direkte oder indirekte Rekursivität: digits = digit * digits È {e} ist nicht zulässig.

egrep unter UNIX

z.B. Real-Zahl: ^[0-9]+\.[0-9]*(E[+-]?[0-9]+)?$

Endliche Automaten

z.B. Lift: kann nur endliche Zustände und endlichen Input haben.

DEA: deterministischer endlicher Automat: bei jedem Zustand ist bekannt, was zu tun ist.

NDEA: nichtDEA mit e-Übergängen.

Definitionen

Endlicher Automat wird beschrieben durch:

• Menge der Zustände
• Eingabealphabet
• Übergangsrelation

Elimination der Î-Übergänge

Zu jedem Automaten mit Î-Übergängen gibt es einen ohne Î-Übergänge, der dieselbe Sprache akzeptiert.

Determinisieren (NEA => DEA)

Zu jedem NEA gibt es einen äquivalenten DEA.

Minimieren von DEAs

Zu jeder regulären Sprache gibt es einen bis auf Umbenennung der Zustände eindeutigen, minimalen DEA.

Zwei Zustände p und q heißen unterscheidbar durch ein Wort w Î S*, wenn mensch von p aus mit w in einen Endzustand gelangen kann, aber nicht von q aus, bzw. von q aber nicht von p aus.

p und q sind ununterscheidbar, wenn sie durch kein Wort unterschieden werden können.

Algorithmus zur Minimierung

Pro Zustandpaar: eine Zelle (leer oder X) und eine Warteliste für Zustandspaare.

1. Hinzufügen einer Falle falls notwendig.

2. Initialisierung: alle Wartelisten sind leer. Alle Paare aus einem End- und einem Nichtendzustand werden mit X markiert.

3. Für jedes nicht-markierte Paar (p, q) prüfe: Gibt es s Î S, sodaß ((d(p,s), d(q,s)) markiert ist, dann markiere (p,q) sowie alle Paare in seiner Warteliste. Andernfalls füge (p,q) zur Warteliste aller Nachfolgerpaare ((d(p,s), d(q,s)) hinzu.

4. Zusammenfassen aller Zustandspaare, die nicht markiert sind, zu einem Zustand.

5. Entfernen aller Zustände, die vom Startzustand aus nicht erreichbar sind oder von denen aus kein Endzustand erreichbar ist.

Grammatiken

Grammatik G = <V,T,P,S>, wobei

V...Variable (Nonterminale)

T...Terminalsymbole

P...Produktionen

S...Startsymbol

Grammatik: Zeichenersetzungssystem

In der endgültigen Sprache sollen nur Terminalsymbole vorkommen, die nicht mehr ersetzt werden.

Backus-Naur-Form (BNF)

Synonym für kontextfreie Produktionen

Notation: Nonterminale in spitzen Klammern.

<Real> => <Digit> <Digits> . <Digits> <SF>

Erweiterte Backus-Naur-Form (EBNF)

Auch "Regular Right Part Grammar (RRPG)"

Auf rechter Seite der Produktionen dürfen reguläre Ausdrücke in EBNF auftreten.

Abkürzung uninteressanter Produktionen:

A=> w1{w2}w3 erlaubt die Ableitung

Chomsky-Hierarchie

Typ 0: alle durch eine Grammatik beschreibbare Sprachen (keine Einschränkungen der Produktionen)

Typ 1: kontextsensitive oder monotone Sprachen

Typ 2: Kontextfreie Sprachen

Typ 3: Reguläre Sprachen

Prädikatenlogik

Elemente: UND, ODER, NICHT, ", $, Konstantensymbole, Funktionssymbole, Prädikatensymbole, Individuenvariablensymbole

Atomformel: z.B. "3 < x" oder auch "2 * x < x - 2" (Term, Prädikatensymbol, Term)

Term: Individuenvariablensymbole, Funktionssymbole, Konstantensymbole

Abstrakter Datentyp: Grundmenge (nicht-leer), Konstantensymbole, Funktionssymbole, Prädikatensymbole

=> Natürliche Zahlen, Binäre Stacks (irreführend, nur 0/1-Strings), Listen

Symbole zu Datentypen

D... abstrakter Datentyp

FS(D), PS(D), KS(D): Funktions-, Prädikaten-, Konstantensymble zu D

Die Sprache EXP (für Expressions)

Einfachste Ausdrücke: Konstanten. Dann Funktionssymbole und Variablensymbole (IVS)

IVS={x, y, z, x₁, x₂ ...}

Sprache der Terme = T:

T: Kleinste Menge, sodaß

• IVS Teilmenge von T (D)
• KS Teilmenge von T (D)
• f Element von FSn(D)

build(rest(nil), x) e T()

x e IVS => x e T()

Funktion M (meaning):

M_T: T(D) => D

D... Grundmenge von D

M_T(I, k) = k'

k'... Konstante zum Symbol k

EXP(D)...Expressions

(E1) IVS Element von EXP

(E2) KS Element von EXP

(E3) f Element FS_n, e₁, .. e_n Element von EXP => F(e₁, .., e_n) Element von EXP

(E4) p Element von PS_n, t, e Element von EXP=> if p(e₁, ..., e_n) then t else e

(E5) F Element von FVS_n, e₁, ..., e_n Element von EXP => F(e₁, ..., e_n)

(FVS = Funktionsvariablensymbole, FVS_n = n-stellige FVS; FVS = {F, G, MEMBER ...})

call-by-value-Funktionsaufruf: Environment wird für die Zeit des Funktionsaufrufs umdefiniert.

call-by-name-Funktionsaufruf: Environment bleibt gleich, die Variablen x₁...x_n werden durch e₁...e_n ersetzt.

Der Unterschied ist, daß bei call-by-value alle Ausdrücke am Anfang ausgewertet werden.

injektive Abbildung: jedes Element von D wird auf ein anderes Element von L abgebildet.

dMM(delta, env, exp) =

if eq?(ART(exp), ivs) then DOIVS(env, exp)

else if eq?(ART(exp), const) then DOCONST(exp)

else if eq?(ART(exp), appl) then DOAPPL(delta, env, exp)

else if eq?(ART(exp), cond) then DOCOND(delta, env, exp)

else if eq?(ART(exp), call) then DOCALL(delta, env, exp)

else error

IVS={x, y, z, x1, ..}

[x]=x, ..., [x1] = x1

KS=[0, 1, 2, ...]

[k]=h(k')                k'...Konstante zum Symbol k

[0]=(), [1] = (1)

[+]=plus

[=]=eq

[<]=lt

dART(exp) = first(exp)

dDOCONST(exp) = 2TES(exp)

dDOIVS(env, exp) =

LOOKUP(2TES(env), exp)

dDOAPPL(delta, env, exp) =

if eq?(FS(exp), plus) then ...