Alfabeth
Een alphabeth is een eindige niet lege verzameling van symbolen. Een alphabeth hoeft niet overeen te komen met wat we in het normale spraakgebruik onder een alfabeth verstaan. Het kan bijvoorbeeld ook uit alleen de symbolen 0 en 1 bestaan. Het kan ook uit een verzameling complexe getallen bestaan. Een alfabeth geven we weer met de griekse letter Sigma: Σ. Voorbeelden van een alfabeth zijn dus: Σ = {a..z}, Σ = {0, 1}, Σ = {(0.1,2.5), (-12.3, 1.0), (2.8, 1.1)}, maar het laatste voorbeeld zal wel nooit praktisch nut hebben.
Woorden
Een woord is niets dan een string bestaande uit symbolen van het alfabeth. De lengte van een woord is niets dan het aantal symbolen waaruit het woord bestaat. Als x een woord is, dan wordt de lengte van x aangeduid met |x|. Als Σ = {0, 1} dan is "011001" een woord van lengte 6. Een bijzonder woord is het woord van lengte 0, het lege woord en aangeduid met de griekse letter epsilon: ε. We definieren voor elke k groter of gelijk aan 0: Σ(k) = {x | x is een woord en |x| = k}
Wiskundige omschrijving van een DFA
Definitie DFA: Een DFA is een quintuple <Σ, S, S0, δ, F>.
-
Σ is het invoeralphabet (eindige niet lege verzamelin symbolen).
-
S is eindige nietlege verzameling van states.
-
S0 is de starttoestand, een element van S.
-
δ is de transitiefunktie : SxΣ -> S.
-
F is de verzameling van final states (of accepting states), een (mogelijk lege) deelverzameling van S.
Een belangrijk element is δ, de transitiefunktie. Deze bepaalt aan de hand van de huidige situatie en een nieuw ingevoerd symbool de nieuwe toestand.
Voorbeeld is frisdrank verkoop: Het alphabeth bestaat uit de waardes van munten. De machine onthoudt hoeveel geld er ingegooid is. De mogelijke totalen zijn de toestanden en toestanden met meer dan 80 eurocent zijn eindtoestanden (er mag een blikje uit de automaat getrokken worden).
Taal
Een taal is een verzameling van geaccepteerde woorden. Om dat wat formeler weer te geven kan men, uitgaande van het alfabeth Σ gebruik maken van de volgende definities:
-
Σ(*)= union(k=0..∞)Σ(k) : de verzameling van alle woorden die met et alphabeth zijn te maken.
-
Σ(+)= union(k=1..∞)Σ(k) : de verzameling van alle niet-lege woorden die met het alphabeth zijn te maken.
Dan is een taal (over alphabeth Σ) een deelverzameling van Σ(*).
Nondeterministic
Er zijn ook Nondeterministic Finite State automata, NDFA's. Geldt bij een DFA dat, uitgaande van een bepaalde toestand, er voor elk invoer-sumbool van Σ er maar één nieuwe toestand mogelijk is (bepaald door de transitiefunktie δ), bij een NDFA zijn er meerdere nieuwe toestnden mogelijk. Als de automaat in een bepaalde toestand is kan de automaat na het lezen van een nieuw invoer-symbool zich in verschillende nieuwe toestanden tegelijk bevinden. Als bij het aanbieden van een nieuw invoer-symbool er vanuit geen van de actieve toestanden een nieuwe toestand bereikt kan worden, dan stopt de automaat. Bij een NDFA is ook de eis van maar één begin-toestand niet van belang: er mogen meerdere begintoestanden zijn.
Een NDFA is een quintuple <Σ, S, S0, δ, F>
-
Σ is het invoeralphabet (eindige niet lege verzamelin symbolen).
-
S is eindige nietlege verzameling van states.
-
S0 een verzameling initiele states, een deelverzameling van S.
-
δ is de transitiefunktie : SxΣ -> ρ(S).
-
F is de verzameling van final states (of accepting states), een (mogelijk lege) deelverzameling van S.
Stelling: Elke taal die herkend wordt door een Nondeterministic Finite state automaat wordt ook herkend door een Deterministic Finite state automaat.
Reguliere talen
...volgt...
De klasse van talen die herkend worden door een Finite state automaat valt precies samen met de klasse van de reguliere talen.