KU Leuven
Automaten en Berekenbaarheid
[B-KUL-G0P84A]
Notities
Tom Sydney Kerckhove
Gestart
19 September 2014
Gecompileerd 23 september 2014
Docent:
Prof. Bart Demoen
Inhoudsopgave
1 Voorkennis
1.1 Verzamelingenleer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Abstracte algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
2
2 Talen en Automaten
2.1 Symbolen en Strings . . . . .
2.2 Talen . . . . . . . . . . . . .
2.3 Reguliere expressies en talen
2.4 Eindige toestandsautomaten
3
3
4
5
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Hoofdstuk 1
Voorkennis
1.1
Verzamelingenleer
Definitie 1.1. Een wiskundige verzameling V is een verzameling van verschillende ongeordende elementen e 1 ,e 2 , . . . ,e 3 .
{V = e 1 ,e 2 , . . . ,en }
We noteren “ei is een element van V ” als volgt.
ei ∈ V
Definitie 1.2. We noemen V 0 een deelverzameling van V als elk element van V 0 ook een element
van V is.
∀v 0 ∈ V 0 ⇒ v ∈ V
Definitie 1.3. De machtsverzameling P (V ) van een verzameling V is de verzameling van alle
deelverzamelingen van die verzameling.
{v | v ⊂ V }
1.2
Abstracte algebra
Definitie 1.4. Een algebra is een verzameling V waarop een aantal inwendige operaties ◦, . . .
gedefinieerd zijn.
∀ v 1 ,v 2 , . . . ,vn ∈ V : z = ◦(v 1 ,v 2 , . . . ,vn ) ∈ V
Definitie 1.5. Een subalgebra is een deelverzameling van een algebra, die op zichzelf ook een
algebra vormt met dezelfde operaties.
2
Hoofdstuk 2
Talen en Automaten
2.1
Symbolen en Strings
Definitie 2.1. Een symbool s is een representatie van een object in de abstractste zin van het
woord.
Definitie 2.2. Een alfabet Σ is een eindige verzameling van symbolen.
Definitie 2.3. Een string s over een alfabet Σ is een geordende opeenvolging van nul, e´ e´ n of
meer elementen van Σ.
Definitie 2.4. ϵ is de string zonder symbolen en noemen we de lege string.
Definitie 2.5. De concatenatie xy van twee strings x = {x 1 ,x 2 , . . . ,xm } en y = {y1 ,y2 , . . . ,yn } is
de volgende geordende verzameling
xy = {x 1 ,x 2 , . . . ,xm ,y1 ,y2 , . . . ,yn }
Eigenschap 2.6. De concatenatie van strings is associatief:
(xy)z = x (yz)
Bewijs.
(xy)z = {x 1 ,x 2 , . . . ,xm ,y1 ,y2 , . . . ,yn }z
= {x 1 ,x 2 , . . . ,xm ,y1 ,y2 , . . . ,yn ,z 1 ,z 2 , . . . ,zo }
= x {y1 ,y2 , . . . ,yn ,z 1 ,z 2 , . . . ,zo }
= x (yz)
Definitie 2.7. De verzameling van alle eindige strings over een alfabet Σ noteren we als Σ∗ .
Σ∗ = {a 1a 2 . . . an | ai ∈ Σ, n,i ∈ N}
3
4
HOOFDSTUK 2. TALEN EN AUTOMATEN
Definitie 2.8. De verzameling Σ ∪ {ϵ } noteren we korter als Σϵ .
CLARIFY: dit is niet zomaar een verzameling sybolen, lijkt het? Is ϵ een symbool of een string?
2.2
Talen
Definitie 2.9. Een taal L over een alfabet Σ is een verzameling van eindige strings over Σ.
Definitie 2.10. De concatenatie L 1L 2 van twee talen L 1 en L 2 over hetzelfde alfabet Σ is de
volgende verzameling:
L 1L 2 = { xy | x ∈ L 1 , y ∈ L 2 }
Eigenschap 2.11. De concatenatie van talen is associatief:
(L 1L 2 )L 3 = L 1 (L 2L 3 )
Bewijs.
(L 1L 2 )L 3 = { xy | x ∈ L 1 , y ∈ L 2 }L 3
= { xyz | x ∈ L 1 , y ∈ L 2 z ∈ L 3 }
= L 1 { yz | y ∈ L 2 , z ∈ L 3 }
= L 1 (L 2L 3 )
Eigenschap 2.12. Talen, uitgerust met de unie, de doorsnede, het complement en de concatenatie,
vormen een algebra.
Bewijs. Inderdaad, zowel de unie, de doorsnede, het complement als de concatenatie zijn inwendig.
Definitie 2.13. De concatenatie van n keer een taal L met zichzelf noteren we als Ln . L0 bevat
enkel de lege string.
L0 = {ϵ }, Ln = LLn−1
Definitie 2.14. De Kleene ster L∗ van een taal L is de unie van alle concatenaties van L met
zichzelf.
∞
[
∗
L =
Ln
n=0
Definitie 2.15. L+ is de unie van L, e´ e´ n of meer keer geconcateneerd met zichzelf.
L+ = LL∗
5
HOOFDSTUK 2. TALEN EN AUTOMATEN
Eigenschap 2.16. We kunnen een taal ook defini¨eren als een deelverzameling van Σ∗ (of als een
element van P (Σ∗ ).)
Bewijs. Inderdaad, elke verzameling van eindige strings is een deelverzameling van de verzameling
van alle eindige strings, alsook een element van de verzameling van alle deelverzamelingen van de
verzameling van alle eindige strings.
Definitie 2.17. L Σ is de notatie voor de verzameling van alle talen over Σ.
L Σ = P (Σ∗ )
2.3
Reguliere expressies en talen
Definitie 2.18. Een reguliere expressie (RE) wordt inductief gedefinieerd als een expressie van
de volgende vorm:
• ϵ
• ϕ
• a met a ∈ Σ
• (E 1 E 2 ) waarbij E 1 en E 2 reguliere expressies zijn over Σ
• (E) ∗ waarbij E een reguliere expressie is over Σ
• (E 1 |E 2 ) waarbij E 1 en E 2 reguliere expressies zijn over Σ
Definitie 2.19. De taal LE bepaald door een reguliere expressie over hetzelfde alfabet Σ is de
volgende.
E
LE
a met a ∈ Σ
{a}
ϵ
ϵ
ϕ
∅
(E 1 E 2 )
LE1LE2
(E)
L∗E
(E 1 |E 2 )
LE1 ∪ LE2
Definitie 2.20. Een reguliere taal is een taal die bepaald wordt daar een reguliere expressie.
Definitie 2.21. ReдLan is verzameling van alle reguliere talen.
Eigenschap 2.22. Reдlan is een subalgebra van L Σ .
Bewijs. Bewijs in delen.
6
HOOFDSTUK 2. TALEN EN AUTOMATEN
• ReдLan is een deelverzameling van L Σ .
ReдLan ⊆ L Σ
• De unie is inwendig in ReдLan.
Kies twee willekeurige reguliere talen LE1 , LE2 ∈ ReдLan. De unie LE1 ∪ LE2 van deze twee
talen wordt bepaald door de reguliere expressie (E 1 |E 2 ) en is bijgevolg een reguliere taal. 1
• De doorsnede is inwendig in ReдLan.
TODO: Bewijs zonder DFA’s te gebruiken.
• Het complement is inwendig in ReдLan.
TODO: Bewijs zonder DFA’s te gebruiken.
• De concatenatie is inwendig in ReдLan.
Kies twee willekeurige reguliere talen LE1 , LE2 ∈ ReдLan. De concatenatie LE1LE2 van deze
twee talen wordt bepaald door de reguliere expressie E 1 E 2 en is bijgevolg een reguliere taal. 2
2.4
Eindige toestandsautomaten
Definitie 2.23. Een niet-deterministische eindige toestandsautomaat (NFA) is een 5-tal (Q, Σ,δ ,qs F )
• Q is een eindige verzameling toestanden.
• Σ is een alfabet.
• δ is de overgangsfunctie van de automaat.
δ : Q × Σϵ → P (Q )
• qs ∈ Q is de starttoestand.
• F ⊆ Q is de verzameling aanvaardbare eindtoestanden.
Definitie 2.24. Een string s wordt aanvaard door een NFA N = (Q, Σ,δ ,qs F ) als s geschreven
kan worden als a 1a 2 . . . an met ai ∈ Σϵ en er een rij toestanden t 1t 2 . . . tn+1 bestaat zodat:
• t 1 = qs
• ti+1 ∈ δ (ti ,ai )
• tn+1 ∈ F
1 Zie
2 Zie
de definitie van de taal bepaald door een reguliere expressie. (Definite 2.19)
de definitie van de taal bepaald door een reguliere expressie. (Definite 2.19)
HOOFDSTUK 2. TALEN EN AUTOMATEN
Definitie 2.25. De taal LM bepaald door een NFA N bevat alle strings die N aanvaardt, en geen
andere strings.
Definitie 2.26. Twee NFA’s N 1 en N 2 zijn emphequivalent als ze dezelfde taal bepalen.
7
© Copyright 2024 ExpyDoc
