Fundamenten van de Informatica Luc De Raedt
Academiejaar 2006-2007 naar de cursustekst van Karel Dekimpe en Bart Demoen
A.1: Talen en Eindige Automaten 1
Deel 1: Inleiding
2
Motivatie Fundamenten van de Informatica • formele basis van de informatica - abstract & wiskundig • onveranderlijk • informatica is ook iets anders dan programmeren ! De rest van de informatica bouwt hierop verder 3
Overzicht Drie delen 1. Automaten en Complexiteit 2. Grafen 3. Vastepuntstheorie
4
Automaten en Complexiteit Automaat : • een formeel, wiskundig model van een computer • verschillende soorten, verschillen naar gelang wat ze kunnen berekenen • Wij: eindige toestands-automaten en Turingmachines 5
Alan Turing (1912 - 1954) • Basis van de informatica a.d.h.v. zijn Turing Machines • Wiskundig model • Notie van berekenbaarheid • Sterke invloed op “Kunstmatige Intelligentie” (o.a. Turing test) • Turing-award 6
Complexiteit Wat kunnen we efficiënt berekenen ? • verschillende klassen van problemen • de ultieme vraag P = NP ? - we weten dat P
NPC NP P
NP
- ook : als er één NP-compleet probleem is dat in P ligt, dan is P = NP - NP-compleet: de moeilijkste problemen in NP 7
Grafen Wat is een graaf ? • knopen + bogen Voorbeelden • computer netwerken • elektriciteitsnetwerken • sociale netwerken 8
Vastepuntstheorie x is een vast punt van een functie f als en slechts als f(x) =x Verschillende eigenschappen Belangrijk voor • semantiek (betekenis) van logica, gegevensbanken en programmeertalen • convergentie van algoritme Wij: een aantal eigenschappen en stellingen (Tarski en Kleene) 9
Praktisch We volgen de cursus tekst • Dekimpe, Demoen, Fundamenten van de Informatica. Online op Toledo. Alles komt online op Toledo • Cursus-tekst +Oefeningen + Slides + Discussie-forum Oefenzittingen gegeven door • Jon Sneyers & Siegfried Nijssen 10
Lessen Dinsdag 14.00-16.00 Vrijdag 14.00-16.00 Maar verschillende lessen vallen weg, o.a. • di 20 februari • vrij 9 maart • di 17 en vrij 20 april • di 1, di 15, vrij 18 mei Kijk naar aankondigingen op Toledo ! 11
A: Inleiding tot Complexiteit
12
A1. Talen en Automaten
13
A1.1. Talen
14
Strings Definitie (1.1.1). Strings over een alfabet. • Een alfabet is een niet-lege eindige verzameling Σ. De elementen van Σ worden symbolen genoemd. • Een string over Σ is een eindige rij symbolen σ1 σ2 · · · σn , waarbij elke σi ∈ Σ. De lengte van een string is het aantal (al dan niet verschillende) symbolen dat gebruikt wordt om de string op te bouwen. • Er is bovendien ´e´en string van lengte 0, de lege string, die we met λ zullen aanduiden. • De verzameling van alle strings over een alfabet Σ duiden we aan met Σ∗
15
Taal Definitie (1.1.2). Een taal. Een taal over een alfabet Σ is een deelverzameling L ⊆ Σ∗ . Neem Σ = {0, 1}.
16
Voorbeelden van Talen 1. L1 = ∅ 2. L2 = Σ∗ = {λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 101, 110, 111, . . .} 3. L3 = {11, 101, 1001, 10001, 100001, . . .} 4. L4 = {λ, 01, 0011, 000111, 00001111, 0000011111, . . .} 5. L5 = {10, 1001110, 000000} 6. L6 = {10, 11, 101, 111, 1011, . . .}
17
Algoritme Met een algoritme bedoelen we een oplossingsmethode • bestaande uit een eindige opeenvolging van instructies, • die elk op precies ´e´en wijze uit te voeren zijn, • en die steeds eindigt. Voor welke talen L bestaat er een algoritme dat herkent of een string s ∈ Σ∗ tot L behoort ? 18
A1.2. Reguliere Expressies en Talen
19
Operaties op Strings Voor een alphabet Σ definieer op Σ∗ volgende operaties: • De concatenatie of samenstelling. Indien x = σ1 σ2 · · · σn ∈ Σ∗ en y = µ1 µ2 · · · µm ∈ Σ∗ dan is hun samenstelling xy = σ1 σ2 · · · σn µ1 µ2 · · · µm ∈ Σ∗ Voorbeeld. Neem Σ = {a, b, c, d}, x = abba en y = abcd dan is xy = abbaabcd. Er geldt voor elke x ∈ Σ∗ dat λx = xλ = x en λλ = λ. 20
Operaties op Strings • Voor x ∈ Σ∗ defini¨eren we x0 = λ ∀n ∈ N : xn+1 = xxn Voorbeeld. Indien x = abb is x3 = abbabbabb. • Met x∗ bedoelen we geen of meer kopie¨en van x. Met andere woorden, een element uit {xn | n ∈ N}. • Met x+ bedoelen we ´e´en of meer kopie¨en van x. Met andere woorden, een element uit {xn | n ∈ N0 }. 21
Operaties op Talen Zij A, B ⊆ Σ∗ , dan is • AB = {ab | a ∈ A, b ∈ B} • A0 = {λ} • ∀n ∈ N : An+1 = AAn • A∗ = A0 ∪ A ∪ A2 ∪ A3 ∪ · · · =
∞ !
n=0
An .
A wordt de Kleenesluiting van A genoemd ∗
• A+ = A ∪ A2 ∪ A3 ∪ · · · = 22
∞ !
n=1
An
Reguliere Taal Definitie (1.2.1). Reguliere Taal. Indien Σ een alfabet is, dan wordt de klasse van alle reguliere talen R over Σ inductief als volgt gedefinieerd: 1. ∅ ∈ R, {λ} ∈ R en ∀σ ∈ Σ : {σ} ∈ R. 2. Indien A, B ∈ R dan ook (A) ∈ R, AB ∈ R, A ∪ B ∈ R en A∗ ∈ R Elke taal uit R wordt een reguliere taal genoemd. 23
Bindingsregels Is A ∪ (BC) = (A ∪ B)C ? Volgorde evaluatie: 1. expressies binnen haakjes 2. Kleene-sluitingen 3. concatenaties 4. unies Dus: A ∪ BC ∗ = A ∪ (B(C ∗ )) ! 24
Voorbeeld Is L = {0110, 01010, 010010, 0100010, 01000010, ...} een reguliere taal ? 1. {0} en {1} zijn reguliere talen 2. {0}{1} en {1}{0} zijn reguliere talen 3. {0}* is een reguliere taal 4. {0}{1}{0}* is een reguliere taal 5. {0}{1}{0}*{1}{0} is een reguliere taal = L 25
Reguliere expressies Reguliere expressies zijn analoog aan reguliere talen. Zij worden vaak gebruik bij het zoeken naar patronen in text of gegevens, bvb. grep en egrep in Unix, Linux, etc. Voorbeelden met Σ = ASCII • 123 en Hallo! en Dag Jef. • ab*c = {ac, abc, abbc, abbbc, ...} • b(ab)*c = {bc, babc, bababc, babababc, ...} • d(i|a)t = {dit, dat} • w((ie)|(at)) = w(ie|at) = {wie, wat} (Volgens voorrangsregels) • d(a|i)*t = {dt, dat, dit, dait, diat, daat, diit, ... } 26
Verdere voorbeelden Voorbeeld. reguliere expressie ab∗ |c a(b∗ |c) (ab)∗ |c
Verzameling van overeenkomstige strings {abn |n ∈ N} ∪ {c} = {a, ab, abb, abbb, abbbb, . . . , c}
{abn |n ∈ N} ∪ {ac} = {a, ab, abb, abbb, abbbb, . . . , ac}
{(ab)n |n ∈ N} ∪ {c} = {λ, ab, abab, abab, ababab, abababab, . . . , c}
27
Reguliere Expressies Definitie (1.2.2). - Reguliere expressie Indien Σ een alfabet is, dan wordt een reguliere expressie over Σ op inductieve wijze als volgt gedefinieerd: 1. ∅ is een reguliere expressie 2. λ is een reguliere expressie 3. Voor elke σ ∈ Σ is σ een reguliere espressie 4. Indien A en B reguliere expressies zijn, dan zijn ook (A), A∗ , A|B en AB reguliere expressies. Elke reguliere expressie bepaalt een reguliere verzameling. 28
Expressies en Talen Stelling (1.2.3). Voor een gegeven alfabet Σ geldt dat de klasse van de reguliere talen op Σ precies samenvalt met de klasse van de reguliere verzamelingen.
Voor elke reguliere taal is er een corresponderende reguliere expressie en vice versa. Bvb. {1}{0}*{1} <-> 10*1 Opmerking: niet alle talen zijn regulier ! bvb.
{0n 1n |n ∈ N}
29
A1.3 Eindige Automaten
30
Eindige Automaten Automaat implementeert algoritme Beschouw 11001 en 1001 0 1
1 Start 01 0
01
Voor elke string in Σ* eindigen we in ⓪ of niet 31
Eindige Automaten Definitie (1.3.1). Een eindige automaat (FSA - Finite State Automaton) is een 5-tal A = (Q, Σ, δ, q0 , F ) • Q een eindige verzameling is. We noemen de elementen van Q de toestanden van de automaat A. • F ⊆ Q is de verzameling van de aanvaardbare eindtoestanden. (De letter F is de eerste letter van het engelse Final). • q0 ∈ Q, deze toestand wordt de begintoestand genoemd. • Σ is een eindige verzameling, het alfabet van de automaat. • δ is een afbeelding, de transitieafbeelding genoemd, δ : Q × Σ → Q. 32
Eindige Automaat • Start in de begintoestand q0 met invoerstring x = σ1 σ2 . . . σn • Per tijdseenheid t := 1...n voer een instructie uit: qit := δ(qit−1 , σt ) (geeft nieuwe toestand). • laatste stap is qin := δ(qin−1 , σn ) • Twee mogelijkheden : – Als qin een aanvaardbare eindtoestand (in F ) is, dan aanvaard x – anders verwerp x 33
Voorbeeld Voorbeeld. We beschouwen een eindige automaat A = (Q, Σ, δ, q0 , F ), met 1. Q = {E, O}, met begintoestand q0 = E. 2. F = {E} 3. Σ = {0, 1}. 4. De afbeelding δ wordt gegeven door volgende tabel δ O E
0 O E
1 E O
34
Voorbeeld (2) De werking van de automaat op de string 1101 is als volgt: 1. Stap 1: de automaat berekent qi1 = δ(q0 , 1) = δ(E, 1) = O. 2. Stap 2: de automaat berekent qi2 = δ(qi1 , 1) = δ(O, 1) = E. 3. Stap 3: de automaat berekent qi3 = δ(qi2 , 0) = δ(E, 0) = E. 4. Stap 4: de automaat berekent qi4 = δ(qi3 , 1) = δ(E, 1) = O !∈ F . De invoerstring 1101 wordt verworpen. 35
Grafisch • Voor elke toestand uit Q tekenen we een cirkel. De toestanden die tot F behoren voorzien we van een dubbele rand. • De begintoestand qo wordt gekenmerkt door een inkomende pijl. • Indien δ(q, σ) = q ! tekenen we een pijl tekenen van de cirkel die toestand q voorstelt, naar de cirkel die toestand q ! voorstelt en we geven het label σ aan deze pijl. Evt. meer labels per pijl. 36
Grafisch 0
1
E
O
1
37
0
Transities voor Strings Definieer een afbeelding δ ∗ op strings: δ ∗ : Q × Σ∗ → Q. De definitie is inductief: 1. ∀σ ∈ Σ, ∀q ∈ Q : δ ∗ (q, σ) = δ(q, σ). 2. Indien x = σ1 σ2 . . . σn ∈ Σ∗ een string is van lengte n ≥ 2, dan: δ ∗ (q, x) = δ ∗ (q, σ1 σ2 . . . σn ) = δ ∗ (δ(q, σ1 ), σ2 . . . σn ). 3. Voor de volledigheid nemen we δ ∗ (q, λ) = q0 .
38
Taal van Automaat Merk op: de automaat zal eindigen in toestand δ ∗ (q0 , x) voor een string x. Ook: de string x wordt aanvaard als en slechts als δ ∗ (q0 , x) ∈ F . Definitie (1.3.2). Taal bepaald door een eindige automaat Indien A = (Q, Σ, δ, q0 , F ) een eindige automaat is, noemen we L(A) = {x ∈ Σ∗ | δ ∗ (q0 , x) ∈ F }
de taal bepaald door de eindige automaat A. Indien voor een gegeven taal L ⊆ Σ∗ geldt dat L = L(A) zeggen we dat A de taal L herkent. 39
Voorbeeld 0
1
E
O
0
1
L(A) = {x ∈ {0, 1}∗ | x bevat een even aantal 1-en}
40
Eindige Automaten en Reguliere Talen Stelling (1.3.3). De klasse van talen die herkend worden door een eindige automaat valt precies samen met de klasse van de reguliere talen.
Zonder bewijs maar illustratie a.d.h.v. voorbeeld. Automaat voor de taal over Σ={a,b} waarvan elke string op bb eindigt. L={a,b}*{bb} 41
Voorbeeld L={a,b}*{bb} Hoe ontwerp ik een automaat ? Welke toestanden moet ik voorzien ? Toestanden ~ geheugen. Bvb. abbbabb a b onthouden 0 1
b b a b ≥2 ≥2 0 1 42
b ≥2
Voorbeeld L={a,b}*{bb} a
b
b q0
q1
q2
a a
43
b
Een niet reguliere taal Bewering: L = {0n 1n |n ∈ N} is niet regulier. Argumentatie. Er bestaat geen eindige automaat die deze taal aanvaard. Stel dat er wel zo’n automaat A = (Q, Σ, δ, q0 , F ) zou bestaan (redenering uit het ongerijmde). Neem aan dat Q = {q0 , q1 , . . . , qn−1 } en beschouw de string x = 0n 1n ∈ L. Verloop van de machine: 44
gelezen symbool nieuwe toestand
q0
0
0
...
0
...
0
...
0
1
1
...
1
q i1
q i2
...
qip
...
qir
...
qin
qin+1
qin+2
...
qi2n !"#$ ∈F
”Pigeonhole principle” - Duiventil principe : ∃p, r : 0 ≤ p < r ≤ n zodat qip = qir . Schrap nu de 0-en van p + 1 tot en met r: gelezen symbool nieuwe toestand
q0
0
...
0
q i1
...
qip−1
0
0
qip qir+1 !"#$
...
0
1
1
...
1
...
qin
qin+1
qin+2
...
qi2n !"#$
=qir
Dan wordt een string aanvaard door de automaat die niet tot de taal behoort.
45
∈F
Een veralgemening Stelling. Het ”pumping lemma” (behoort niet tot de examenstof ) Als L een reguliere taal is, dan bestaat er een getal p (de ”pumping” lengte) zodat als s ∈ L en lengte(s) ≥ p dan kan s geschreven worden als s = xyz waarbij x, y, z strings zijn die aan de volgend voorwaarden voldoen: • ∀i ∈ N : xy i z ∈ L • lengte(y) > 0 (dus y $= λ) • lengte(xy) ≤ p
46
Bewering: L = {0n 1n |n ∈ N} is niet regulier. Argumentatie: Een bewijs uit het ongerijmde gebruik makende van het pumping lemma. Stel L is regulier en kies s = 0p 1p waarbij p de pumping lengte is. Dan kunnen we s schrijven als xyz zodat xy i z ∈ L voor i ≥ 0. Er zijn nu drie mogelijkheden voor y: • y bestaat alleen uit 0-en. Maar dan heeft de string xyyz ook tot L behoren, maar er zijn meer 0-en dan 1-en. Dit is een contradictie volgens de definitie van L. • y bestaat alleen uit 1-en. Analoge redenering. • y bestaat uit zowel 0-en als 1-en. Maar dan moet de string xyyz ook tot L behoren, maar in deze string wordt de volgorde van 0 en 1 niet gerespecteerd. 47
A1.4 Niet Deterministische Automaten
48
Niet-deterministische Automaten
Niet-determinisme: er bestaan verschillende mogelijkheden voor de volgende toestand Basis voor parallelle verwerking Wij: automaten + Turing-machines
49
Niet-deterministische Automaten Definitie (1.4.1). Een niet-deterministische eindige automaat Een niet deterministische eindige automaat is een 5-tal A = (Q, Σ, δ, q0 , F ) waarbij • Q een eindige verzameling van toestanden. • F ⊆ Q is de verzameling van aanvaardbare eindtoestanden. • q0 ∈ Q, de begintoestand van de automaat. • Σ is een eindige verzameling, het alfabet. • δ is een afbeelding δ : Q × (Σ ∪ {λ}) → P(Q). P(Q) = {X | X ⊆ Q}: is de verzameling van alle deelverzamelingen van Q. 50
Voorbeeld a, b
q0
b
q1
b
q2
Merk op: • niet noodzakelijk een transitie voor elk symbool vanuit een knoop • meerdere transities voor één symbool vanuit een knoop mogelijk • ook transities voor λ mogelijk String abb: 3 mogelijkheden.
51
Transities voor Strings Breidt δ voor symbolen uit naar δ ∗ voor strings naar analogie met de deterministische automaten. Voorbeeld. Voor de niet deterministische eindige automaat van daarnet is 1. δ ∗ (q0 , abb) = {q0 , q1 , q2 }
a, b
2. δ ∗ (q0 , abab) = {q0 , q1 }
q0
3. δ ∗ (q0 , aaaaaaa) = {q0 } 52
b
q1
b
q2
Taal van de Automaat Definitie (1.4.2). Taal aanvaard door een niet deterministische automaat. Indien A = (Q, Σ, δ, q0 , F ) een niet deterministische eindige automaat is, noemen we L(A) = {x ∈ Σ∗ | δ ∗ (q0 , x) ∩ F #= ∅} de taal bepaald door de eindige automaat A. Indien voor een gegeven taal L ⊆ Σ∗ geldt dat L = L(A) zeggen we dat A de taal L herkent. Voorbeeld. Welke taal herkent onze automaat ?
L = {a, b}∗ {bb} 53
Eigenschap Stelling (1.4.3). Elke taal die herkend wordt door een niet deterministische eindige automaat wordt eveneens herkend door een deterministische eindige automaat.
54
Voorbeeld Voorbeeld. We zoeken een niet deterministische eindige automaat die de taal L = {a}∗ {b}∗ {c}∗ op het alfabet Σ = {a, b, c} herkent.
55
Eigenschap Voor elke reguliere taal L bestaat er een nietdeterministische automaat die L herkent.
56
Eigenschap Voor elke reguliere taal L bestaat er een nietdeterministische automaat die L herkent. Bewijs door inductie: L=∅
L = {λ} L = {σ}
57
Reguliere Taal Definitie (1.2.1). Reguliere Taal. Indien Σ een alfabet is, dan wordt de klasse van alle reguliere talen R over Σ inductief als volgt gedefinieerd: 1. ∅ ∈ R, {λ} ∈ R en ∀σ ∈ Σ : {σ} ∈ R. 2. Indien A, B ∈ R dan ook (A) ∈ R, AB ∈ R, A ∪ B ∈ R en A∗ ∈ R Elke taal uit R wordt een reguliere taal genoemd. 58
Inductie Stap Een machine met taal A
Een machine met taal AB
59
Inductie Stap Met taal A B
Met taal A*
60
Besluit Reguliere talen, expressies en eindige automaten (zowel deterministisch als niet deterministisch) definiëren dezelfde soort van talen Automaten worden vaak gebruikt bij modellering Er bestaan ook probabilistische uitbreidingen (bvb. (Hidden) Markov Modellen), en uitbreidingen die een uitvoer produceren (“transducers”) Reg. expressies worden soms ook gebruikt als patroon voor het vinden van strings Deze talen zijn wel beperkt ({0n1n | n is een natuurlijke getal}) 61
