Deterministisk endelig automat (DFA)

En DFA er en femtuppel M = (S, I, f, s₀, F) der S er en endelig mengde tilstander, I er inngangsalfabetet, f: S × I → S er overgangsfunksjonen (total og enverdig), s₀ ∈ S er starttilstanden og F ⊆ S er de aksepterende tilstandene. «Deterministisk» betyr at det for hvert par (tilstand, symbol) finnes nøyaktig én etterfølger. I et tilstandsdiagram markeres s₀ med en kildeløs innkommende pil og aksepterende tilstander med dobbel sirkel.

Aksept: En streng w aksepteres av M hvis lesing av w fra s₀, symbol for symbol via f, ender i en tilstand i F. Formelt med utvidet overgangsfunksjon: w ∈ L(M) ⟺ f̂(s₀, w) ∈ F, der f̂(s, λ) = s og f̂(s, wc) = f(f̂(s,w), c). Spesielt: λ ∈ L(M) ⟺ s₀ ∈ F.

Regulære uttrykk og Kleene-stjerne

Regulære uttrykk bygges fra ∅, λ og enkeltsymboler ved hjelp av konkatenasjon, union (∪) og Kleene-stjerne (*). Kleene-stjernen er definert som A* = A⁰ ∪ A¹ ∪ A² ∪ …, der A⁰ = {λ}. Dermed inneholder A* alltid den tomme strengen. A⁺ = A·A* er «én eller flere» og utelater λ (hvis λ ∉ A). Kleenes teorem garanterer at de språkene som beskrives av regulære uttrykk er nøyaktig de som gjenkjennes av endelige automater — de regulære språkene.

Vanlige mønstre: «inneholder x»: (a∪b)*x(a∪b)*. «slutter på x»: (a∪b)*x. «starter med x»: x(a∪b)*. «partall antall x»: spore paritet med 2 tilstander. «nøyaktig k forekomster av a»: b*ab*a…ab* med k a-er.

Telling av aksepterte strenger

For å telle strenger av lengde n som en DFA aksepterer, la aₛ(n) være antall lengde-n-strenger som fører fra s₀ til tilstand s. Da gjelder rekursjonen aₛ(n) = Σ_{(t,c): f(t,c)=s} aₜ(n−1), med aₛ₀(0)=1 og aₛ(0)=0 ellers. Svaret er Σ_{s∈F} aₛ(n). Ofte er det enklere å bruke et komplement-argument: tell totalt (kⁿ) og trekk fra de uønskede.

Eksempel 1 — DFA for «inneholder aa», og telling:

Tilstander: s₀ (ingen relevant a), s₁ (sist sett én a), s₂ (aa funnet — felle, aksepterende).

Overganger: f(s₀,a)=s₁, f(s₀,b)=s₀; f(s₁,a)=s₂, f(s₁,b)=s₀; f(s₂,a)=s₂, f(s₂,b)=s₂. Start s₀, F={s₂}.

Tell lengde 4 via komplement: strenger UTEN «aa» av lengde n følger Fibonacci f(n): f(0)=1, f(1)=2, f(2)=3, f(3)=5, f(4)=8.

Totalt lengde 4: 2⁴ = 16. Aksepterte (med «aa») = 16 − 8 = 8.

Eksempel 2 — regulært uttrykk og telling for «partall antall 0-er» over {0,1}:

DFA: to tilstander q₀ (partall 0-er, aksepterende) og q₁ (oddetall). 1 holder tilstanden; 0 bytter mellom q₀ og q₁.

Regulært uttrykk: 1*(0 1* 0 1*)* — vilkårlige 1-ere, så blokker som hver tilfører to 0-er.

Tell lengde 4: trenger partall antall 0-er, altså 0, 2 eller 4 nuller blant 4 posisjoner.

Antall = C(4,0) + C(4,2) + C(4,4) = 1 + 6 + 1 = 8.

Studieguide: Endelige tilstandsmaskiner og formelle språk

Studieguide: Endelige tilstandsmaskiner og formelle språk