Dozent: Helmut Alt
Website zur Vorlesung kommt noch
pro Vorlesung 3- 4 Stunden
Themen
Automatentheorie
formale Sprachen
Berechenbarkeit
Komplexität
Kapitel:
- reguläre Sprachen und Ausdrücke, Grammatiken, endliche Automaten
- kontextfreie Sprachen und kontextfreie Grammatiken (John Backus, Noam Chomsky), Kellerautomaten (Pushdown-Automaten)
- Berechenbarkeit, Entscheidbarkeit von Sprachen(David Hilbert 1900, Kurt Gödel 1930, Turing 1930),rekursiv aufzählbare Sprachen, Turingmaschinen
- Textverarbeitung, Hardwareentwicklung, lexikalische Analyse
- Syntax von Programmiersprachen, Parser
Kapitel 1: grundlegende Definitionen, reguläre Ausdrücke und Sprachen, endliche Automaten
Definitionen
∑ sei endliche Menge: Alphabet
Elemente von ∑ heißen: Zeichen oder Symbole
BSP:- ∑={0,1}: Binäralphabet
- ∑={A,....,Z}
- ASCII
- UNICODE
Def: ∑* - Menge aller endlichen Folgen über ∑: Wörter über ∑ einschlißlich der Folge der Länge 0 (leeres Wort,ε)
Länge eines Worts : Anzahl der Zeichen |w|
Konkatenation zweier Worte
w_1,w_2 € ∑*: beide Folgen "aneinandergehängt" w_1°w_2 (° kann auch weggelassen werden)
BSP: ∑={0,1}
∑*={ε, 0,1,00,01,10,11,...}
es gibt |∑|^k Worte der Länge k in ∑*
Spezialfall: ∑={} => ∑*={ε}
Bemerkungen
a) |w_1°w_2| =|w_1| +|w_2| für alle w_1,w_2 €∑*
b) w°ε=w = ε°w für alle w €∑*; ε ist neutrales Element bzgl Konkat.
c) (w_1°w_2)°w_3=w_1°(w_2°w_3)für alle w_1,w_2,w_3 €∑*;
Assoziativgesetz bedeutet (∑*,°) ist eine Halbgruppe
Halbgruppe mit neutr. Element heißt auch Monoid
∑*: freies Monoid über ∑
|..|: (∑* ,*)-> (ℕ,+) ist ein Halbgruppenhomomorphismus wg a)
Def: Sei ∑ Alphabet, u,v∈∑*
u heißt Präfix von v genau dann, wenn (gdw) w€∑* existiert mit v=u°w
u heißt Suffix von v gdw w∈∑* mit v=w°u
u heißt Teilwort von v gdw w_1,w_2 €∑* existieren mit v=w_1°u°w_2
Bsp: ∑={0,1} v=010
Präfixe : ε,0,01 heißt eine Formale Sprache über ∑.
Beispiele: 1. ∑={a,...,z,A,...Z} L= {w∈∑* | w ist ein Wort der deutschen Sprache}
={Aachen,...,Zytoxität}
2. gleiches ∑
L={w∈∑*| w ist Palindrom}
L={ε,a,....,z,A,...Z,anna,...,otto,...,uhu,...,reliefpfeiler,...}
3.∑={0,1}
L={w∈{0,1}*| w ist Binärdarstellung einer durch 3 teilbaren Zahl}
{0,11,...,1111,...}
5. ∑={0,1}
L= {0^n 1^n 0^n|n∈|N}
={ε,010,001100,....}
6. ∑ beliebig L={ε}
7. ∑ beliebig L={∅}
Operationen zwischen Sprachen
sei ∑ Alphabet L,L_1,L_2 Sprachen
L_1°L_2 = {w_1°w_2|w_1∈L_1, w_2 ∈L_2}
Bsp: {ε,0,11}°{00,11} ={00,11,000,011,...}
L*={w∈∑*| w lässt sich zerlegen w=w_1°w_2°...°w_n mit w_i ∈L i=1,...n ∪{ε}}
10.02.2013
L*={w_1...w_k|w_i∈L, i=1...k}
Mit hilfe dieser Operationen und der Vereinigung lassen sich aus einfachen Sprachen komplexere konstruieren,
z.B. ∑={a,b}
L={a,b}* °{a} °{a,b}
L={w∈{a,b}*|das zweitletzte Zeichen von w ist a}
kann auch geschrieben werden:
({a}u{b})*°{a}°({a}u{b}) (a|b)*a(a|b)
Def: Sei ∑ ein Alphabet. Definieren Menge R_∑ der regulären Ausdrückee über ∑ induktiv wie folgt:
R_∑ ist eine Sprache über ∑ ∪{∅,(,),*,|}
1. ∅ und jedes a∈∑ ist ∈R_∑
2.α, β∈R_∑ => (αβ)∈R_∑
3. α, β∈R_∑ => (α|β)∈R_∑
4. α∈R_∑ => α*∈R_∑
5. R_∑ ist die kleinste Menge (bzgl ⊆), die 1. bis 4. erfüllt
Bsp: Behauptung:
(((0|1)*0)(0|1)) ∈R_∑ ∑={0,1}
0∈R_∑; 1∈R_∑ (Regel 1)
0|1 ∈R_∑ (Regel 3)
(0|1)* ∈R_∑ (Regel 4)
((0|1)*0)∈R_∑(Regel 2)
L(α)={w∈{0,1}* vorletztes Zeichen von w ist eine 0}
Definition:
Jedem regülären Ausdruck α über ∑ wird eine Sprache L(α) zugeordnet, und zwar
1. L(∅)=∅
L(a)={a} für alle a∈∑
2. L(αβ)=L(α)°L(β) für alle αβ∈R_∑
3.L((α|β))=L(α)uL(β)
4.L(α*)=(L(α))*
Beispiele:
BSP2 L={w∈{0,1}*|w enthält 10 nicht als Teilwort}
L=L(α) mit L=0*1*
BSP3 Suchen regulären Ausdruck α mit L(α) ={w∈{0,1}*|w enthält 101 nicht als Teilwort}
α=(0*1*100)*0*1*(∅*|10) tut es
Anmerkung: L(∅*)={ε}
Beweis: a)L⊆L(α)
sei w ∈L
betrachten alle vorkommen von 10 in w
w=w_1 10 w_2 10... w_k 10...w_(k+1)
auf jedes 10 muss eine 0 folgen außer am Ende.
w=w'_1 100.... w'_2 100... w'_k 100 w'_(k+1)
wobei w'_1=w_1
w_2=0 w'_2
w_(k+1) =0 w_(k+1)
w'_i enthalten 10 nicht mehr als Teilwort, d.h. (Bsp2) w'_1 ∈ L(0*1*) i=1,...,k+1
als w∈L((0*1*100)*0*1*(∅*|10)) (0*1*100)*=w'_1....w'_k 100
(0*1*)=w'_(k+1)
(∅*|10)=u
b) L(α)⊆L, sei w∈L(α). Dann hat w die Form (0*1*100)*0*1*(∅*|10)
in solchen Worten kommt 101 nicht vor => w€L
Definition: Sei ∑ ein Alphabet. Eine Sprache L⊆∑* heißt regulär gdw. es einen regulären Audruck α€R_∑ gibt mit L=L(α)
Siehe Bsp. von vorher
es gilt auch: jede endliche Sprache ist regulär
Endliche Automaten (EA)
bildlich: | | | | | | | | <- Band besteht aus Zellen das Zeichen eines Alphabets ∑ enthalten
^ |Lesekopf von Links nach rechts
endliche Kontrolle endlich viele mögliche Zustände (q)
1 Schritt : Automat ließt ein Zeichen a, abhängig vom gelesenen Zeichen und seinem momentanen Zustand q, geht er über in einen neuen Zustand q' und bewegt den Kopf um 1 Zelle nach rechts
gewisse Zustände gelten als (akzeptierende) Endzustände.
Eingabewort w gilt als akzeptiert gdw es ganz gelesen wurde und der Automat in einem Endzustand ist
Menge aller akz. Wörter : "akzeptierte Sprache"
z.B. L={w€{0,1}*|das vorletzte Zeichen von w ist 0}
q0:startzustand
q0,q1,q2,q3: Zustände (einfacher Kreis)
q2,q3:akzeptierender Endzustand (Doppelter Kreis)
qo: 1 q0
0 q1
q1: 0 q2
1 q3
q2: 0 q2
1 q3
q3: 1 q0
0 q1
a
(q)--->(q1)
Bedeutung: wenn EA in q ist und ein a ließt dann geht er zu q1 über
{ε,01,0011,000111....} kann nicht von EA akzeptiert werden (kein Merken)
Definition: Ein EA ist ein 5-Tupel M=(Q,∑,δ,q0,F)
wobei Q: endliche Menge der Zustände
∑: Eingabealphabet
δ: ∑xQ -> Q Überführungsfunktion
q0: Startzustand
F⊆Q: Menge der Endzustände
Bsp: (siehe oben)
M=(Q,∑,δ,q0,F)
Q={q0,q1,q2,q3}
∑={0,1}
δ=
(qo,1)->q0
(q0,0)->q1
(q1,0)->q2
(q1,1)->q3
(q2,0)->q2
(q2,1)->q3
(q3,1)->q0
(q3,0)->q1
q0=q0
F={q2,q3}
Sonderzeichen: √, ∤, |, ≥, ≤, ∑, ⊕, ≠, , ○, ⚡, Σ, π, ✓, ∞, ρ
≡, ∈, ∉, ∀, ∃, ∅, ⋂, ⋃, ∪, ⊂, ⊃, ⊆, ⊇, ⋀, ⋁, ¬, ≈
⇒, ⇔, ⟼, ↤, ☇, →, ↔, ↓, /,\
Ā, Ē, Ū, Ō, Ω, ɸ, ω, τ, ℕ, ℤ, α, β, γ, δ, ε, ⌈,⌉, ⌊,⌋