Formale Sprachen /

Automatentheorie
Kapitel 1. Sprachen

Prof. Homeister
Agenda

• Motivation

• Alphabete

• Sprachen

2
Let´s go shopping

Der Supermarkt um die Ecke hat zwei Schiebetüren.

- Eingang
- Ausgang
3
Eingang

Nähert sich eine Person, öffnet sich die Tür.

Die Tür schließt sich, nachdem die Person hindurchgetreten ist.

4
Modell des Eingangs

Die Tür kann geöffnet /

geschlossen werden.

Matten mit Sensoren

Vordere Hintere
Matte Matte
Personen betreten
- die vordere Matte
- die hintere Matte
- beide Matten
Tür - keine der Matten

5
Modell des Eingangs – (2)

Tritt eine Person auf die vordere

Matte, öffnet sich die Tür (sofern
geschlossen).

Ist jemand auf der hinteren

Vordere Hintere
Matte Matte Matte, so geschieht nichts.

Sind beide Matten leer, schließt

sich die Tür (sofern offen).

Tür

6
Modell des Eingangs – (3)

Zwei Zustände der Tür:

offen, geschlossen („zu“).

Vier Eingabesignale (von Sensoren in den Matten):

vorn, hinten, keine, beide

Vorgänge, Zustandsübergänge:

KEINE VORN HINTEN BEIDE

ZU zu offen zu offen
OFFEN zu offen offen offen
7
Zustandsgraph

VORN, BEIDE
KEINE, VORN,
zu offen HINTEN,
HINTEN
BEIDE
KEINE

Zeitliche Entwicklung, bzgl. Folge von Eingangssignalen:

keine, keine, vorn, hinten, keine, vorn, beide, beide, hinten,
keine, keine, …

Hinweise: das ist KEIN endlicher Automat (s. nächstes Kap.) 8

Kaffeeautomat
Dieser
②
Zustands
E
- &0 , 50

o
• akzeptiert 1,- € oder -,50 € Münzen ↓
↳
1
,0
0 ,5

• besitzt einen Ausgabeknopf

Werden
• mind. 1,50 € gezahlt, und
• die Kaffeetaste gedrückt OZ
gezahlt

gibt‘s Kaffee!
↓
⑭Ausge
e

Übung: Modelliere den Kaffeeautomaten

- wähle Eingabesignale
- wähle sinnvolle Zustände
- zeichne ein Zustandsdiagramm

9
Kaffeeautomat: Modell
Abkürzung:
O – 1,- € (one Euro)
F – -,50 € (fifty Cents)
C – Ausgabeknopf (Coffee)

Beispiele:
OFC, FFFCF, OOC, OCOC füllen den Becher
OC, CC, OOOO, OCO machen uns nicht wach

10
Zustandsgraph -

C C

O
z0 z100

F, O F, O, C
F F

O E 15
z50 zpaid zcoffee
C
1

Endzustand
C F, O

11
Methodenreflektion
Was tut unser Modell? gibt kein Rückgeld aus

Zeichenketten untersuchen… strings als

möglich untersuchen

OFC, FFFCF, OOC, OCOC füllen den Becher

OC, CC, OOOO, OCO machen uns nicht wach

12
Agenda

• Motivation

• Alphabete

• Sprachen

13
Ein natürliches Alphabet (Menge von
Symbolen/Zeichen)

Sanskrit

Wir verwenden eine abstrakte

Definition.
Ziel: automatische Verarbeitung

14
Formale Alphabete

Ein Alphabet ist eine endliche, nichtleere Menge von Zeichen oder
Symbolen.

S
Beispiel: - igma
>
1 = {0,1}
2 = {a,b,c}
3 = {a,…,z,A,…,Z}
4 = {KEINE,HINTEN,VORN,BEIDE}
5 = {O,F,C}

15
Formale Alphabete – (2)
ascii ist das Alphabet aller ASCII-Symbole in der Praxis verwenden
wir Unicode

16
Wörter
Eine Folge von Symbolen eines Alphabets  ist ein Wort.

Bsp. mit  = {a,b,c}:

abbc
c
cccccccb

Bsp. 2:  = {KEINE,HINTEN,VORN,BEIDE}
Damit
KEINE KEINE HINTEN VORN BEIDE KEINE
ist ein Wort aus sechs Symbolen (Leerzeichen dienen der
Lesbarkeit).

17
Wörter – (2)
* ist die Menge aller Wörter über .

Beispiel:
 = {a,b,c},
* = {,a,b,c,aa,ab,ac,ba,bb, …} >
-
Größe :
nur leeres Wort

oder unendlich

ε ist das leere Wort (Länge 0, keine Zeichen)

ε ist stets in * enthalten.

Beachte:
• a kann Zeichen aus  sein
• a kann ein Wort der Länge Länge 1 aus * sein
wird vom Kontext bestimmt
18
Wortlänge
|w| bezeichnet die Länge eines Worts.

Beispiel:
|01100| = 5

Rekursiv definiert:
|ε| = 0
|wa| = |w| + 1 mit a Zeichen aus , w Wort aus *.

|w|a bezeichnet die Anzahl der Vorkommen des Zeichens a im

Wort w.
Beispiel:
|01100|0 = 3
19
Operationen
• Konkatenation:
w, v 2 *.
v · w oder vw: v und w aneinandergehängt.

Beispiel:  = {a,b,…,z}, sun 2 *, glasses 2 *.

sun · glasses = sunglasses

· wird meist ausgelassen.

Eigenschaften:
|v · w| = |v| + |w|
ε·v=v
v·ε=v
20
Operationen – (2)
• Potenz:
Bsp: (bla)2 = blabla
Definition: Für w 2 *:
w0 = ε
wn = wn-1 · w für n>0

Nützlich, um Mengen von Wörtern zu definieren:

L = {a2bn | n ¸ 0}
ist die Menge aller Strings, die mit zwei as beginnen, worauf
beliebig viele bs folgen dürfen.

L = {aa, aab, aabb, aabbb, …}

Übung: Was ist L´ = {a(bc)n | n ¸ 1} ?

21
Agenda

• Motivation

• Alphabete

• Sprachen

22
Formale Sprache
Eine Sprache ist eine Menge von Wörtern über einem Alphabet Σ.
Oder: Eine Sprache ist eine Teilmenge von *.

Bsp. Sprachen über Σ = {0,1}:

L = {00, 1, 0100101}
Leven, die Menge aller Wörter mit einer geraden Anzahl 0en
d.h. Leven = {w in * : |w|0 gerade}

Eine Sprache über Σascii:

Lnumbers, die Menge der korrekt gebildeten ganzen Zahlen in C.

6771, 0, -61551 in Lnumbers

xq?%, 04541, 61-551 nicht in Lnumbers

23
Beispiel: die Kaffeesprache

Alphabet {O,F,C}

OFC, FFFCF, OOC, OCOC füllt den Becher

OC, CC, OOOO, OCO macht uns nicht wach

OFC, FFFCF, OOC, OCOC sind Elemente einer Sprache;

wir nennen diese Lcoffee

OC, CC, OOOO, OCO  Lcoffee

Lcoffee beschreibt die Problemstellung vollständig.

24
Wofür formale Sprachen?
Die tägliche Arbeit eines Compilers:
Der Programmierer gibt eine Zeichenkette ein, z.B.:

for (i=0;i<5;i++)
println(i);

Der Compiler überprüft, ob diese Zeichenkette einem syntaktisch

korrekten Programm entspricht,
oder:
Ist die Zeichenkette ein Wort in LC-Programs?

25
Das Wortproblem
Die Aufgabe, algorithmisch zu bestimmen, ob eine Zeichenkette in
der Sprache liegt, heißt Wortproblem.
Eingabe: Sprache L, Wort w
Ausgabe: Ja, falls w2 L; Nein, sonst.

Sprache L w2L wL

Lnumbers w ist eine wohl- w ist keine korrekte
geformte ganze Zahl ganze Zahl

LC-Programs w ist ein syntaktisch w entspricht keinem

korrektes synt. korrektem
C-Programm C-Programm.
LJava-Classes … …
26
Anwendung des Wortproblems

Problemstellung im Compilerbau:
Teste, ob ein
Spezifikation einer
Programm
Programmiersprache
syntaktisch korrekt ist

Formale Sprache,
z.B. Ljava Teste, ob w 2 Ljava

27
Vorgriff: Compiling-Phasen
• Lexikalische Analyse:
Folge von Zeichen → Folge von Tokens

• Syntaktische Analyse (Parsing):

untersuche syntaktische Struktur, erzeuge Syntaxbaum

• Semantische Analyse:
Syntaxbaum mit Attributen, prüft die Typen von Bezeichnern: z.B.
type casts, ein string wird einem integer Bezeichner
zugeordnet o.ä.

• Synthese: Erzeugung von Maschinencode:

Zwischencode, Optimierung, Codeerzeugung

Detailliert in Kapitel 6.
28
Punkte 1 und 2 mit Gegenständen dieser Veranstaltung leistbar.
Thank you very much!

29