Teh­tä­vä:
DFA-pe­rus­asioi­ta

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Täs­sä teh­tä­väs­sä opis­kel­laan de­ter­mi­nis­ti­siin ää­rel­li­siin au­to­maat­tei­hin eli DFA:hin liit­ty­viä pe­rus­kä­sit­tei­tä ja har­joi­tel­laan päät­te­ly­ta­po­ja. Ne luo­vat poh­jan, jon­ka va­raan voi­daan ra­ken­taa mie­len­kiin­toi­sia so­vel­luk­sia.

1. DFA:n mää­ri­tel­mä
2. Po­lut ja sil­mu­kat
3. DFA:n hy­väk­sy­mä kie­li
4. Tur­hat ti­lat
5. Lo­puk­si

DFA:n mää­ri­tel­mä

Ohei­nen ku­va esit­tää eräs­tä DFA:ta. Sa­ma ku­va on py­sy­väs­ti ruu­dun oi­keas­sa ala­nur­kas­sa. Ker­taam­me al­ka­jai­sik­si DFA:n ma­te­maat­ti­sen mää­ri­tel­män se­kä osien ni­met ja piir­ros­mer­kin­nät. Mää­ri­tel­mä on al­la tii­viis­ti ja sen pe­räs­sä on ky­sy­myk­siä. Mal­li­vas­tauk­set tu­le­vat nä­ky­viin siir­tä­mäl­lä kur­so­ri rus­kean alueen pääl­le.

Mil­lä ni­mel­lä Q:n al­kioi­ta kut­su­taan ja mi­ten ne piir­re­tään? vas­tausNii­tä kut­su­taan ti­loik­si. Ti­lat piir­re­tään yk­sin- tai kak­sin­ker­tai­si­na ym­py­röi­nä.

Mi­kä on ku­van DFA:n Q? vas­taus{1, 2, 3, 4, 5, 6}

Mil­lä ni­mel­lä Σ:aa kut­su­taan? Mil­lä ni­mel­lä Σ:n al­kioi­ta kut­su­taan? Mi­ten Σ il­mais­taan piir­rok­ses­sa? vas­tausΣ:aa kut­su­taan aak­kos­tok­si ja sen al­kioi­ta kut­su­taan mer­keik­si. Jol­lei erik­seen ole muu­ta sa­not­tu, Σ on piir­rok­ses­sa kaar­ten yh­tey­des­sä esiin­ty­vien merk­kien jouk­ko.

Mi­kä on ku­van DFA:n Σ? vas­taus{a, b}

Mi­tä ε ∉ Σ tar­koit­taa? vas­tausε tar­koit­taa tyh­jää merk­ki­jo­noa eli nol­las­ta mer­kis­tä koos­tu­vaa merk­ki­jo­noa. ε ∉ Σ tar­koit­taa, et­tä tyh­jää merk­ki­jo­noa ei voi käyt­tää merk­ki­nä. Tä­tä on tär­keää ko­ros­taa sik­si, et­tä on pal­jon DFA:lta näyt­tä­viä piir­rok­sia, jois­sa ε esiin­tyy kaa­ren yh­tey­des­sä ikään kuin se oli­si merk­ki. Nii­tä on pal­jon, kos­ka NFA:n kaa­ren ni­me­nä voi ol­la tyh­jä merk­ki­jo­no eli ε. Voi­ko ε esiin­tyä DFA:n kaa­ren ni­me­nä? vas­tausEi voi.

Mi­tä Σ* tar­koit­taa? vas­tausΣ* tar­koit­taa kaik­kien Σ:n al­kiois­ta muo­dos­tet­ta­vis­sa ole­vien jo­no­jen eli kaik­kien merk­ki­jo­no­jen jouk­koa. Jos Σ = {a}, niin Σ* = …{ε, a, aa, aaa, …} Jos Σ = {a, b}, niin Σ* = …{ε, a, b, aa, ab, ba, bb, aaa, …} Jos Σ = ∅, niin Σ* = …{ε}

Mil­lä ni­mel­lä δ:n al­kioi­ta kut­su­taan ja mi­ten ne piir­re­tään? vas­tausSen al­kioi­ta kut­su­taan kaa­rik­si. Kaa­ri (q, a, q’) piir­re­tään nuo­le­na, jo­ka al­kaa ti­las­ta q, päät­tyy ti­laan q’ ja jon­ka vie­res­sä on merk­ki a.

Mi­tä tar­koit­taa, et­tä δ on osit­tai­nen funk­tio jou­kol­ta Q × Σ jou­kol­le Q? vas­tausSe tar­koit­taa en­sin­nä­kin, et­tä δ on jouk­ko kol­mi­koi­ta muo­toa (q, a, q’), mis­sä a on merk­ki ja q ja q’ ovat ti­lo­ja. Li­säk­si se tar­koit­taa, et­tä sii­hen ei kuu­lu kah­ta kol­mik­koa, jot­ka eroa­vat toi­sis­taan vain vii­mei­sen osan osal­ta; toi­sin sa­noen, mis­tään ti­las­ta ei läh­de mil­lään mer­kil­lä useam­paa kuin yk­si kaa­ri. ”Funk­tio” tar­koit­tai­si, et­tä jo­kai­ses­ta ti­las­ta läh­tee jo­kai­sel­la mer­kil­lä ta­san yk­si kaa­ri. ”Osit­tai­nen” väl­jen­tää tä­tä si­ten, et­tä ti­las­ta ei tar­vit­se läh­teä kaa­ria jo­kai­sel­la mer­kil­lä. (Jo­pa se on sal­lit­tua, et­tä mis­tään ti­las­ta ei läh­de lain­kaan kaa­ria.)

Toi­si­naan käy­täm­me funk­tio­kut­su­mer­kin­tää δ(q, a). Jos (q, a, q’) on kaa­ri, niin δ(q, a) = q’. Jos δ(q, a) = q’, niin (q, a, q’) on kaa­ri. Va­li­tet­ta­vas­ti funk­tio­kut­su­mer­kin­tä on köm­pe­lö sil­loin, kun q:sta ei läh­de a-ni­mis­tä kaar­ta. Sik­si käy­täm­me pal­jon kaa­ri­mer­kin­tää (q, a, q’).

Mi­kä on ku­van DFA:n δ? vas­taus{(1, a, 4), (2, a, 6), (2, b, 5), (3, b, 2), (4, b, 5), (5, a, 6), (5, b, 5), (6, a, 3)}

Luet­te­le ne δ(q, a), jot­ka ei­vät ole mää­ri­tel­lyt ku­van DFA:ssa. vas­tausδ(1, b), δ(3, a), δ(4, a) ja δ(6, b)

Jos A on jouk­ko, niin |A| tar­koit­taa A:n ko­koa eli al­kioi­den mää­rää. Se on jo­ko luon­nol­li­nen lu­ku 0, 1, 2, … tai ää­re­tön. Mil­loin δ on mah­dol­li­sim­man pie­ni, ja kuin­ka pal­jon |δ| on sil­loin? vas­tausSil­loin kun kaa­ria ei ole lain­kaan. Sil­loin |δ| = 0. Mil­loin δ on mah­dol­li­sim­man suu­ri, ja kuin­ka pal­jon |δ| on sil­loin? vas­tausSil­loin kun jo­kai­ses­ta ti­las­ta läh­tee kaa­ri jo­kai­sel­la mer­kil­lä. Sil­loin |δ| = |Q||Σ|. Kuin­ka pal­jon ovat ku­van DFA:n |δ|, |Q|, |Σ| ja |Q||Σ|? vas­taus|δ| = 8, |Q| = 6, |Σ| = 2 ja |Q||Σ| = 12.

Mil­lä ni­mel­lä q̂:ta kut­su­taan ja mi­ten se piir­re­tään? vas­tausq̂ on al­ku­ti­la. Se osoi­te­taan piir­rok­ses­sa nuo­lel­la, jo­ka päät­tyy sii­hen ja al­kaa tyh­jäs­tä (siis ei ala ti­las­ta).

Mi­tä q̂ ∈ Q tar­koit­taa? vas­tausSe tar­koit­taa, et­tä al­ku­ti­la on ti­la (ei­kä esi­mer­kik­si merk­ki). Se, et­tä al­ku­ti­la on ti­la, ei ma­te­maat­ti­ses­sa mää­ri­tel­mäs­sä seu­raa sii­tä, et­tä sa­na ”ti­la” on sa­nan ”al­ku­ti­la” lop­pu­osa, kos­ka ni­met ei­vät ole osa ma­te­maat­tis­ta mää­ri­tel­mää. Si­tä­pait­si ei­hän täl­lai­seen voi luot­taa edes luon­nol­li­ses­sa kie­les­sä, sil­lä puo­li­to­tuus ei ole to­tuus ei­kä penk­ki­ur­hei­lu ole ur­hei­lua.

Mi­kä on ku­van DFA:n q̂? vas­taus1

Mil­lä ni­mel­lä F:n al­kioi­ta kut­su­taan ja mi­ten ne piir­re­tään? Mi­tä F ⊆ Q tar­koit­taa? vas­tausNii­tä kut­su­taan lop­pu­ti­loik­si ja ne piir­re­tään kak­sin­ker­tai­si­na ym­py­röi­nä. F ⊆ Q tar­koit­taa, et­tä jo­kai­nen lop­pu­ti­la on ti­la.

Mi­kä on ku­van DFA:n F? vas­taus{3, 4}

Edel­lä yh­den ”Mi­kä on ku­van DFA:n x” -ky­sy­myk­sen vas­tauk­ses­sa ei esiin­ny merk­ke­jä { ja }. Mis­sä ja mik­si? vas­tausq̂ on yk­si ti­la, mut­ta muut DFA:n osat ovat jouk­ko­ja.

Tyh­jää jouk­koa mer­ki­tään ∅. Jo­kai­sel­le DFA:n osal­le Q, Σ, δ, q̂ ja F ker­ro, voi­ko se ol­la ∅, ja jos ei voi niin pe­rus­te­le mik­si. vas­tausQ ≠ ∅, kos­ka q̂ ∈ Q. Sa­ma suo­mek­si: ti­lo­jen jouk­ko ei voi ol­la tyh­jä, kos­ka al­ku­ti­la kuu­luu sii­hen. Σ, δ ja F voi­vat ol­la tyh­jiä. Jos ol­laan oi­kein tark­ko­ja, niin q̂ voi ol­la tyh­jä jouk­ko. Tä­mä joh­tuu sii­tä, et­tä ei ole ra­jat­tu si­tä, mi­tä ti­loi­na voi ol­la. Sik­si ti­loi­na voi ol­la jouk­ko­ja, ja toi­si­naan niin teh­dään­kin. Tä­mä on kui­ten­kin niin hie­no­va­rai­nen asia, et­tä vas­taus ”q̂ ei voi ol­la tyh­jä jouk­ko, kos­ka se ei ole jouk­ko” on täs­sä vai­hees­sa kurs­sia täy­sin hy­väk­syt­tä­vä.

Mik­si ää­rel­li­syyt­tä ei vaa­di­ta δ:lta ja F:ltä, vaik­ka ky­se on de­ter­mi­nis­ti­sis­tä ää­rel­li­sis­tä au­to­maa­teis­ta? vas­tausF on Q:n osa­jouk­ko­na kor­kein­taan yh­tä suu­ri kuin Q, ja Q on ää­rel­li­nen, jo­ten myös F on ää­rel­li­nen. Edel­lä to­det­tiin, et­tä |δ| ≤ |Q||Σ|, jo­ka on ää­rel­li­nen, kos­ka Q ja Σ ovat ää­rel­li­siä.

Piir­rä DFA, jon­ka muut osat kuin q̂ ovat mah­dol­li­sim­man pie­net. vas­taus

Math­Check ei osaa ää­rel­li­siä au­to­maat­te­ja, mut­ta se osaa jo­ta­kin, jol­la nii­tä voi mat­kia teh­tä­vien kan­nal­ta riit­tä­vän hy­vin. Ti­lat mer­ki­tään isoil­la kir­jai­mil­la. Al­ku­ti­lan kir­jain on mää­rät­ty teh­tä­väs­sä, mut­ta muut saat va­li­ta it­se, el­lei toi­sin sa­no­ta. Aak­kos­toa ei mer­ki­tä. Ti­las­ta läh­te­vät kaa­ret se­kä tie­to, on­ko ti­la lop­pu­ti­la, esi­te­tään tä­hän tyy­liin:

A ::= aD
B ::= aF | bE
C ::= "" | bB

Kes­kim­mäi­nen ri­vi esit­tää kaa­ret (B, a, F) ja (B, b, E). Alin ri­vi esit­tää kaa­ren (C, b, B) ja ker­too, et­tä C on lop­pu­ti­la. Jos ti­la ei ole lop­pu­ti­la ei­kä sii­tä läh­de kaa­ria, sil­le ei teh­dä omaa ri­viä. Al­ku­ti­la on se ti­la, jo­ka mai­ni­taan en­sim­mäi­se­nä. Vä­lien ja ri­vin­siir­to­jen käyt­tö on mel­ko va­paa­ta kah­ta sään­töä lu­kuun­ot­ta­mat­ta:

• Kaa­ren mer­kin (ku­ten a) ja kär­ki­pään ti­lan (ku­ten D) pi­tää ol­la kiin­ni toi­sis­saan (ku­ten aD).
• Nii­den pe­räs­sä tu­lee ol­la vä­li­lyön­ti, ri­vin­siir­to tai vas­tauk­sen lop­pu. Jol­lei ole, niin Math­Check luu­lee si­nun yrit­tä­vän esit­tää jo­tain muu­ta ja saat­taa an­taa vai­kea­ta­jui­sen vir­he­il­moi­tuk­sen!

Täy­den­nä ku­van DFA:n esi­tys val­miik­si. Ku­van ti­la­nu­me­rot vas­taa­vat Math­Checkin iso­ja kir­jai­mia tau­lu­kon mu­kai­ses­ti.

ku­vas­sa	1	2	3	4	5	6
kir­joi­ta	A	B	C	D	E	F

ok_text Oi­kein! CFG_set A ::= aD B ::= aF | bE C ::= "" | bB D ::= "" | bE E ::= aF | bE F ::= aC ; CFG_set2 A ::= aD B ::= aF | bE C ::= "" | bB D ::= E ::= F ::= ; CFG_compare
tai

Math­Check ei tar­kas­ta an­noit­ko oi­kean DFA:n, vaan hy­väk­syy­kö an­ta­ma­si DFA oi­kean kie­len. Sik­si vas­tauk­sek­si kel­paa myös jo­kin muu DFA, jo­ka hy­väk­syy sa­man kie­len. Ko­kei­le vaih­ta­mal­la kaa­ren (2, b, 5) ti­lal­le (2, b, 2)! Vih­jeKor­vaa ri­vi
   B ::= aF | bE
ri­vil­lä
   B ::= aF | bB
.

Tee vas­tauk­seen jo­kin muu­tos, jo­ka muut­taa hy­väk­syt­tyä kiel­tä ja ko­kei­le, min­kä­lai­nen il­moi­tus tu­lee.

Ko­kei­le toi­sen ri­vin pai­kal­la seu­raa­vat ja kat­so, min­kä­lai­nen il­moi­tus tu­lee.
B ::= aF| bE
B ::= aF|bE
B::=aF |bE

Po­lut ja sil­mu­kat

DFA:n pol­ku tar­koit­taa jo­noa q₀a₁q₁a₂q₂⋯q_n, mis­sä n ≥ 0, q₀ ∈ Q ja jo­kai­sel­la 1 ≤ i ≤ n pä­tee (q_i−1, a_i, q_i) ∈ δ. Sen pi­tuus on n. Pol­ku on siis yh­tä eri­kois­ta­paus­taMyös yk­si ti­la on pol­ku. Se saa­daan mää­ri­tel­mäs­tä va­lit­se­mal­la n = 0, jol­loin jo­no on pelk­kä q₀. Jo­no, jos­sa on nol­la kaar­ta, on eri asia, kos­ka se jät­tää ker­to­mat­ta, mi­kä on se yk­si ti­la q₀. Tä­tä ha­vain­nol­lis­te­taan hie­man jäl­jem­pä­nä pää­teks­tis­sä. lu­kuun­ot­ta­mat­ta olen­nai­ses­ti sa­ma asia (vaik­ka eri ta­val­la il­mais­tu­na) kuin jo­no kaa­ria, jos­sa seu­raa­va kaa­ri al­kaa sii­tä ti­las­ta mis­sä edel­li­nen kaa­ri lop­puu. Ma­te­maat­ti­nen po­lun mää­ri­tel­mä vas­taa siis var­sin hy­vin sa­nan ”reit­ti” mer­ki­tys­tä yk­si­suun­tais­ten ka­tu­jen ver­kos­tos­sa. Po­lun pi­tuus on sii­nä ole­vien kaar­ten mää­rä.

Luet­te­le ku­van DFA:n kaik­ki ti­las­ta 4 al­ka­vat po­lut, joi­den pi­tuus on enin­tään 2. vas­taus4
4b5
4b5a6
4b5b5

pol­ku		jo­no kaa­ria
q0
q0a1q1		(q0, a1, q1)
q0a1q1a2q2		(q0, a1, q1)(q1, a2, q2)
q0a1q1a2q2a3q3		(q0, a1, q1)(q1, a2, q2)(q2, a3, q3)

Mik­si po­lun mää­ri­tel­mäs­sä osis­ta q₁, …, q_n ei tar­vit­se sa­noa, et­tä ne ovat ti­lo­ja, ja osis­ta a₁, …, a_n ei tar­vit­se sa­noa, et­tä ne ovat merk­ke­jä, vaik­ka osas­ta q₀ tar­vit­si sa­noa, et­tä se on ti­la? vas­tausJou­kon δ eli kaar­ten mää­ri­tel­mä ta­kaa yh­des­sä eh­don (q_i−1, a_i, q_i) ∈ δ kans­sa, et­tä a_i on merk­ki ja q_i on ti­la kun 1 ≤ i ≤ n. Jos n > 0, niin ne ta­kaa­vat myös et­tä q₀ on ti­la, kos­ka se on kaa­ren (q₀, a₁, q₁) al­ku­pää. Jos n = 0, niin ”jo­kai­sel­la 1 ≤ i ≤ n pä­tee (q_i−1, a_i, q_i) ∈ δ” ei lu­paa mi­tään. Riit­täi­si sa­noa ”jos n = 0 niin q₀ on ti­la”, mut­ta on yk­sin­ker­tai­sem­paa sa­noa ”q₀ on ti­la”.

Pol­ku q₀a₁q₁⋯q_n al­kaa q₀:sta ja päät­tyy q_n:ään, eli on q₀:sta q_n:ään. Il­maus ”q:sta pää­see q’:uun” tar­koit­taa, et­tä on ole­mas­sa pol­ku q:sta q’:uun. Jos σ ∈ Σ* eli σ on merk­ki­jo­no, niin q:sta pää­see σ:lla q’:uun ja q =σ⇒ q’ tar­koit­ta­vat, et­tä on ole­mas­sa sel­lai­nen pol­ku q₀a₁q₁⋯q_n, et­tä q₀ = q, a₁a₂⋯a_n = σ ja q_n = q’.

Luet­te­le kaik­ki σ, joi­den pi­tuus on enin­tään 6 ja joil­le pä­tee 6 =σ⇒ 6 ku­van DFA:ssa. vas­tausε
aba
abba
abbba
abaaba
abbbba

Mil­lä eh­dol­la pol­ku q₀a₁q₁⋯q_n voi­daan liit­tää po­lun r₀b₁r₁⋯r_m pe­rään si­ten, et­tä niis­tä tu­lee yk­si pol­ku? vas­tausq₀ = r_m Mis­tä min­ne näin saa­tu pol­ku vie, ja mil­lä merk­ki­jo­nol­la? vas­tausSe vie r₀:sta q_n:ään b₁⋯b_ma₁⋯a_n:llä. Mi­ten se il­mais­taan q =σ⇒ q’-mer­kin­näl­lä? vas­tausr₀ =b₁⋯b_ma₁⋯a_n⇒ q_n

Jo­kai­sel­le q ∈ Q on ole­mas­sa ai­na­kin yk­si sel­lai­nen σ ja q’, et­tä q =σ⇒ q’. Ne ovat …ε ja q. Siis jo­kai­sel­le q ∈ Q pä­tee q =ε⇒ q. Tä­mä seu­raa sii­tä, et­tä jo­kai­ses­ta ti­las­ta pää­see it­seen­sä kul­ke­mal­la nol­la kaar­ta.

Sil­muk­ka tar­koit­taa pol­kua, jon­ka pi­tuus on vä­hin­tään 1 ja jon­ka en­sim­mäi­nen ja vii­mei­nen ti­la ovat sa­mat. Esi­mer­kik­si 2a6a3b2b5a6a3b2 on ku­van DFA:n sil­muk­ka. Yk­sin­ker­tai­nen sil­muk­ka tar­koit­taa sil­muk­kaa, jos­sa mi­kään ti­la ei tois­tu si­tä lu­kuun­ot­ta­mat­ta, et­tä vii­mei­nen ti­la on sa­ma kuin en­sim­mäi­nen. Esi­mer­kik­si 2a6a3b2b5a6a3b2 ei ole ku­van DFA:n yk­sin­ker­tai­nen sil­muk­ka, mut­ta 2b5a6a3b2 on.

Luet­te­le ku­van DFA:n kaik­ki yk­sin­ker­tai­set sil­mu­kat, jois­sa ti­la 5 ei esiin­ny. vas­taus2a6a3b2
6a3b2a6
3b2a6a3
(Kaik­ki kol­me ovat eri sil­mu­koi­ta, kos­ka ne al­ka­vat eri ti­las­ta.)

Huo­maam­me, et­tä jo­kai­nen yk­sin­ker­tai­nen sil­muk­ka, jon­ka pi­tuus on n, tuot­taa n − 1 muu­ta yk­sin­ker­tais­ta sil­muk­kaa, jot­ka ovat muu­ten sa­ma kuin al­ku­pe­räi­nen sil­muk­ka, mut­ta kier­tä­mi­nen aloi­te­taan eri koh­das­ta. Jot­ta jo­kais­ta niis­tä ei tar­vit­si­si mai­ni­ta erik­seen, seu­raa­vis­sa teh­tä­vis­sä pyy­de­tään mai­nit­se­maan niis­tä vain se, jos­sa kier­tä­mi­nen aloi­te­taan mah­dol­li­sim­man pie­ni­nu­me­roi­ses­ta ti­las­ta.

Luet­te­le ku­van DFA:n kaik­ki sel­lai­set yk­sin­ker­tai­set sil­mu­kat, joi­den en­sim­mäi­nen ti­la on nu­me­ro­ar­vol­taan pie­nin sil­mu­kas­sa esiin­ty­vä ti­la. vas­taus5b5
2a6a3b2
2b5a6a3b2

Luet­te­le ku­van DFA:n kaik­ki sel­lai­set sil­mu­kat, joi­den pi­tuus on 5 tai 6, ja joi­den en­sim­mäi­nen ti­la on nu­me­ro­ar­vol­taan pie­nin sil­mu­kas­sa esiin­ty­vä ti­la. vas­taus5b5b5b5b5b5
5b5b5b5b5b5b5
2b5b5a6a3b2
2b5b5b5a6a3b2
2a6a3b2a6a3b2

Edel­lä to­te­sim­me, et­tä jo­kai­nen yk­sin­ker­tai­nen sil­muk­ka, jon­ka pi­tuus on n, tuot­taa n − 1 muu­ta yk­sin­ker­tais­ta sil­muk­kaa, jot­ka ovat muu­ten sa­ma kuin al­ku­pe­räi­nen sil­muk­ka, mut­ta kier­tä­mi­nen aloi­te­taan eri koh­das­ta. Pä­tee­kö sa­ma sil­mu­koil­le? vas­tausEi pä­de. Esi­mer­kik­si 2a6a3b2a6a3b2 tuot­taa vain kol­me eri sil­muk­kaa, vaik­ka sen pi­tuus on 6. Ku­van DFA:lla on jo­pa sil­muk­ka, jon­ka pi­tuus on 6, ja jos­ta saa­daan kaik­kiaan vain yk­si sil­muk­ka aloit­ta­mal­la kier­tä­mi­nen eri koh­das­ta. Se on tä­mä5b5b5b5b5b5b5.

DFA:n hy­väk­sy­mä kie­li

Mää­ri­tel­mä DFA:n (Q, Σ, δ, q̂, F) hy­väk­sy­mä kie­li tar­koit­taa nii­den σ jouk­koa, joil­le on ole­mas­sa sel­lai­nen q ∈ F, et­tä q̂ =σ⇒ q. Ti­lan q ∈ Q hy­väk­sy­mä kie­li tar­koit­taa DFA:n (Q, Σ, δ, q, F) hy­väk­sy­mää kiel­tä.

Luet­te­le kuu­si mah­dol­li­sim­man ly­hyt­tä merk­ki­jo­noa, jot­ka kuu­lu­vat ku­van DFA:n hy­väk­sy­mään kie­leen. vas­tausa
abaa
abbaa
abbbaa
abbbbaa
abaabaa

Aak­kos­to on {a, b, c}. An­na mah­dol­li­sim­man pie­net DFA:t, joi­den hy­väk­sy­mät kie­let ovat seu­raa­van­lai­set. Käy­tä al­ku­ti­lan ni­me­nä A. Va­lit­se it­se mui­den ti­lo­jen ni­met.

• Ne merk­ki­jo­not, jois­sa ei ole kah­ta a:ta pe­räk­käin.
  ok_text Oi­kein! CFG_set A ::= "" | aB | bA | cA B ::= "" | bA | cA ; CFG_set2 A ::= ; CFG_compare
  tai lunt­taus
• Ne merk­ki­jo­not, jois­sa on ai­na­kin kak­si a:ta ja täs­mäl­leen yk­si b.
  ok_text Oi­kein! CFG_set A ::= aB | bD | cA B ::= aC | bE | cB C ::= aC | bF | cC D ::= aE | cD E ::= aF | cE F ::= aF | cF | "" ; CFG_set2 A ::= ; CFG_compare
  tai lunt­taus
• Ne merk­ki­jo­not, jois­sa ei ole c:tä ja jot­ka lop­pu­vat abaa. Tä­mä on täs­sä vai­hees­sa kurs­sia vai­kea, mut­ta voi­daan tuot­taa myö­hem­min esi­tet­tä­vil­lä tek­nii­koil­la. Jol­let löy­dä oi­keaa vas­taus­ta, voit kat­soa tä­män teh­dyk­si kun olet yrit­tä­nyt to­sis­sa­si vii­des­ti. (Tä­män kal­tai­sil­le on käyt­töä muun muas­sa kun sa­tel­liit­ti­pai­kan­nin synk­ro­noi­tuu tai­vaal­ta tu­le­vaan sig­naa­liin löy­tä­mäl­lä sii­tä sa­tel­lii­tin tun­nis­teen.)
  ok_text Oi­kein! Täs­sä vie­lä ku­va: #<img src=#"http://users.jyu.fi/%7eava/DFA_lopussa_abaa.png#" alt=#"[abaa-lop­pu­vat merk­ki­jo­not hy­väk­sy­vän ää­rel­li­sen au­to­maa­tin ku­va]#"#> CFG_set A ::= aB | bA B ::= aB | bC C ::= aD | bA D ::= aE | bC E ::= aB | bC | "" ; CFG_set2 A ::= ; CFG_compare
  tai

DFA:n ra­ken­tees­ta voi mel­ko hel­pos­ti pää­tel­lä joi­ta­kin asioi­ta sen hy­väk­sy­mäs­tä kie­les­tä.

• DFA:n hy­väk­sy­mä kie­li on ∅ jos ja vain jos …Al­ku­ti­las­ta ei pää­se yh­teen­kään lop­pu­ti­laan.
• DFA:n hy­väk­sy­mä kie­li on ää­rel­li­nen jos ja vain jos …Ei ole ole­mas­sa sil­muk­kaa, jo­hon pää­see al­ku­ti­las­ta ja jos­ta pää­see ai­na­kin yh­teen lop­pu­ti­laan. Huo­maa, et­tä ”pää­see ai­na­kin yh­teen lop­pu­ti­laan” to­teu­tuu myös sil­loin, kun sil­mu­kas­sa on lop­pu­ti­la.
• DFA:n hy­väk­sy­mä kie­li on Σ* jos ja vain jos …Jo­kai­nen ti­la, jo­hon al­ku­ti­las­ta pää­see, on lop­pu­ti­la ja sii­tä läh­tee kaa­ri jo­kai­sel­la Σ:n al­kiol­la.

Seu­raa­vak­si osoi­tam­me, et­tä jo­kai­sel­le ää­rel­li­sel­le kie­lel­le on ole­mas­sa DFA, jo­ka hy­väk­syy sen. Konst­ruk­tio on hy­vin yk­sin­ker­tai­nen. Tä­mä DFA hy­väk­syy kie­len {ahven, hei, heinä, hepo}.

Konst­ruk­tio voi­daan il­mais­ta ma­te­maat­ti­ses­ti seu­raa­vas­ti. Ol­koon L = {σ₁, …, σ_n} ⊆ Σ* ää­rel­li­nen kie­li. Jos L = ∅, niin on vain al­ku­ti­la. An­nam­me sen ni­mek­si ε. Jos L ≠ ∅, niin jo­kais­ta L:ään kuu­lu­van merk­ki­jo­non jo­kais­ta al­ku­osaa koh­den muo­dos­te­taan ti­la. Al­ku­osaa voi­daan sel­lai­se­naan käyt­tää ti­lan ni­me­nä. Mui­ta ti­lo­ja ei ole. Esi­mer­kis­sä ti­loik­si saa­daan {ε, a, ah, ahv, ahve, ahven, h, he, hei, hein, heinä, hep, hepo}. Al­ku­ti­la on ε. Jos a₁⋯a_k−1a_k on ti­la mis­sä k > 0, niin (a₁⋯a_k−1, a_k, a₁⋯a_k−1a_k) on kaa­ri, ja mui­ta kaa­ria ei ole. Esi­mer­kik­si (ahv, e, ahve) on kaa­ri mut­ta (ahv, a, hein) ei ole kaa­ri. Lop­pu­ti­lat ovat L:ään kuu­lu­vat ti­lat. Esi­mer­kis­sä ne ovat ahven, hei, heinä ja hepo.

Mik­si tä­mä konst­ruk­tio ei kel­paa, jos DFA:n hy­väk­sy­mä kie­li on ää­re­tön? vas­tausSyn­tyi­si ää­ret­tö­män mon­ta ti­laa, mi­kä rik­koo vaa­ti­mus­ta, et­tä ti­lo­jen jouk­ko on ää­rel­li­nen.

Mik­si tar­vit­si kä­si­tel­lä tyh­jä kie­li eri­kois­ta­pauk­se­na? vas­tausJot­ta al­ku­ti­la oli­si ti­la. Jos kie­li ei ole tyh­jä, niin ε saa­daan kie­leen kuu­lu­van sa­nan (min­kä ta­han­sa) al­ku­osa­na. Jos kie­li on tyh­jä, niin sa­no­jen al­ku­osia ei ole lain­kaan, jo­ten ε ei tu­le si­tä kaut­ta.

Tur­hat ti­lat

Jos ti­laan q ei pää­se al­ku­ti­las­ta, niin q ei voi ol­la osa al­ku­ti­las­ta jo­hon­kin lop­pu­ti­laan vie­vää pol­kua. Sel­lai­sen q:n, sii­hen päät­ty­vien kaar­ten ja sii­tä al­ka­vien kaar­ten pois­ta­mi­nen ei muu­ta DFA:n hy­väk­sy­mää kiel­tä.

Mik­si ti­lan pois­ta­mi­nen vaa­tii, et­tä myös sii­hen kyt­key­ty­vät kaa­ret pois­te­taan? vas­tausPiir­rok­ses­ta ti­lan voi pois­taa il­man, et­tä sii­hen kyt­key­ty­vät kaa­ret pois­te­taan. Sil­loin syn­tyy kaa­ria, joi­den nuo­len­kär­ki osoit­taa tyh­jää tai jot­ka al­ka­vat tyh­jäs­tä. Täl­lai­nen olen­to ei kui­ten­kaan ole DFA, kos­ka se ei kai­kil­ta osin to­teu­ta DFA:n ma­te­maat­tis­ta mää­ri­tel­mää. Se rik­koo si­tä vaa­ti­mus­ta, et­tä δ on osit­tai­nen funk­tio jou­kol­ta Q × Σ jou­kol­le Q. Tä­mä vaa­ti­mus si­säl­tää sen, et­tä jo­kai­nen kaa­ri al­kaa ti­las­ta (”jou­kol­ta Q × Σ”) ja päät­tyy ti­laan (”jou­kol­le Q”).

Ole­te­taan, et­tä ti­lat ja kaa­ret on to­teu­tet­tu tie­tuei­na si­ten, et­tä kaa­ri­tie­tuees­ta on osoi­tin kaa­ren kär­ki­pään ti­lan tie­tuee­seen. Mi­kä oh­jel­moin­nis­sa laa­jal­ti huo­no­na pi­det­ty asia voi ta­pah­tua, jos ti­la pois­te­taan il­man, et­tä sii­hen kyt­key­ty­vät kaa­ret pois­te­taan? vas­tausJos kaa­ren kär­ki­pään ti­la pois­te­taan, niin osoi­tin sii­hen osoit­taa va­pau­tet­tuun muis­tiin. Täs­tä voi seu­ra­ta vir­he­toi­min­to­ja, var­sin­kin jos muis­ti ote­taan myö­hem­min oh­jel­man suo­ri­tuk­sen ai­ka­na muu­hun käyt­töön.

Myös­kään ti­la, jos­ta ei pää­se mi­hin­kään lop­pu­ti­laan, ei voi ol­la osa al­ku­ti­las­ta jo­hon­kin lop­pu­ti­laan vie­vää pol­kua. Sen­kään pois­ta­mi­nen ei muu­ta DFA:n hy­väk­sy­mää kiel­tä, kun­han pois­ta­mi­nen to­teu­te­taan oi­kein. Mi­ten se to­teu­te­taan oi­kein? vas­tausTi­laan kyt­key­ty­vät kaa­ret on pois­tet­ta­va, ja li­säk­si on vie­lä yk­si sään­tö, mi­kä? vas­tausAl­ku­ti­laa ei saa pois­taa, vaik­ka sii­tä ei pää­si­si­kään mi­hin­kään lop­pu­ti­laan. Mää­ri­tel­män mu­kaan q̂ ∈ Q eli DFA:lla on ai­na ol­ta­va al­ku­ti­la.

Mik­si äs­ken mai­nit­tua li­sä­sään­töä ei tar­vin­nut sa­noa kun edel­lä pu­hut­tiin sel­lais­ten ti­lo­jen pois­ta­mi­ses­ta, joi­hin ei pää­se al­ku­ti­las­ta? vas­tausAl­ku­ti­la ei ole sel­lai­nen ti­la. Al­ku­ti­las­ta pää­see it­seen­sä kul­ke­mal­la pol­ku, jon­ka pi­tuus on nol­la.

Vaik­ka tä­män teh­tä­vän laa­ti­ja yrit­ti ol­la hy­vin huo­lel­li­nen, hän unoh­ti edel­lä ti­lan pois­ta­mi­seen liit­ty­vän sään­nön, jon­ka huo­ma­si vas­ta oi­ko­lu­kies­saan teh­tä­vän. Mi­kä sään­tö puut­tuu? vas­tausPois­tet­ta­va ti­la pi­tää pois­taa myös lop­pu­ti­lo­jen jou­kos­ta F. Al­ku­pe­räi­ses­sä DFA:ssa voi ol­la tur­hia lop­pu­ti­lo­ja, joi­hin ei pää­se al­ku­ti­las­ta.

Mää­ri­tel­mä DFA:n muu ti­la kuin al­ku­ti­la on tur­ha jos ja vain jos al­ku­ti­las­ta ei pää­se sii­hen tai sii­tä ei pää­se mi­hin­kään lop­pu­ti­laan. Al­ku­ti­la ei ole tur­ha.

Lau­se 1 Jos DFA:sta pois­te­taan tur­hat ti­lat ja nii­hin kyt­key­ty­vät kaa­ret, niin DFA:n hy­väk­sy­mä kie­li ei muu­tu. (Pois­tet­ta­vat lop­pu­ti­lat pi­tää pois­taa myös lop­pu­ti­lo­jen jou­kos­ta.)

Jos tur­hia ti­lo­ja ei ole, niin seu­raa­vat pä­te­vät:

• DFA:n hy­väk­sy­mä kie­li on ∅ jos ja vain jos …DFA:ssa ei ole lop­pu­ti­laa. (Sil­loin sii­nä on vain yk­si ti­la.)
• DFA:n hy­väk­sy­mä kie­li on ää­rel­li­nen jos ja vain jos …DFA ei si­säl­lä sil­muk­kaa tai ei si­säl­lä yh­tään lop­pu­ti­laa.
• DFA:n hy­väk­sy­mä kie­li on Σ* jos ja vain jos …Jo­kai­nen ti­la on lop­pu­ti­la ja sii­tä läh­tee kaa­ri jo­kai­sel­la Σ:n al­kiol­la.

Toi­si­naan ha­lu­taan, et­tä ti­la­siir­ty­mä­funk­tio on seu­raa­vas­sa mie­les­sä täy­si.

DFA:n ti­la­siir­ty­mä­funk­tio on täy­si, jos ja vain jos δ(q, a) on mää­ri­tel­ty jo­kai­sel­le q ∈ Q ja jo­kai­sel­le a ∈ Σ.

Ker­ro sel­keäl­lä suo­men­kie­lel­lä, mi­tä täy­si ti­la­siir­ty­mä­funk­tio tar­koit­taa DFA-piir­ros­ten kan­nal­ta. vas­tausJo­kai­ses­ta ti­las­ta eli yk­sin- tai kak­sin­ker­tai­ses­ta ym­py­räs­tä läh­tee jo­kai­sel­la aak­ko­sel­la kaa­ri. (Useam­man kuin yh­den sa­man­ni­mi­sen kaa­ren läh­te­mi­nen sa­mas­ta ti­las­ta on jo­ka ta­pauk­ses­sa kiel­let­ty DFA:ssa. Vaa­ti­mus ”täy­si” sul­kee pois mah­dol­li­suu­den, et­tä ti­las­ta läh­tee jol­lain mer­kil­lä nol­la kaar­ta.)

Jos ohei­sen ku­van esit­tä­män DFA:n ti­la­siir­ty­mä­funk­tio on täy­si, niin mi­kä on DFA:n aak­kos­to? vas­taus∅ eli tyh­jä jouk­ko.

Jos ti­la­siir­ty­mä­funk­tion ha­lu­taan ole­van täy­si, niin voi ol­la vält­tä­mä­tön­tä, et­tä DFA:ssa on ai­na­kin yk­si tur­ha ti­la. Täs­mäl­li­sem­min sa­noen, on ole­mas­sa kie­liä, jot­ka voi hy­väk­syä DFA:lla, mut­ta ei mil­lään sel­lai­sel­la DFA:lla, jos­sa ei ole tur­hia ti­lo­ja ja jon­ka ti­la­siir­ty­mä­funk­tio on täy­si. Ol­koon L kie­li, jon­ka jo­kin DFA hy­väk­syy. An­na sel­lai­nen L:ää ku­vaa­va eh­to, et­tä jos ja vain jos se to­teu­tuu, niin L:n voi hy­väk­syä DFA:lla, jos­sa ei ole tur­hia ti­lo­ja ja jon­ka ti­la­siir­ty­mä­funk­tio on täy­si. vas­tausJo­ko L = ∅, tai jo­kai­sel­la σ ∈ Σ* on ole­mas­sa sel­lai­nen ρ ∈ Σ*, et­tä σρ ∈ L. Eh­dos­sa on siis yleis­sään­tö ja li­säk­si yk­si eri­kois­ta­paus. Yleis­sään­tö sa­noo, et­tä jo­kai­sel­la merk­ki­jo­nol­la on sel­lai­nen jat­ke, et­tä jat­ket­tu merk­ki­jo­no kuu­luu L:ään. Eri­kois­ta­pauk­se­na L on tyh­jä kie­li.

Eh­don voi pe­rus­tel­la osoit­ta­mal­la, et­tä yk­kö­ses­tä seu­raa kak­ko­nen ja kak­ko­ses­ta seu­raa yk­kö­nen, mis­sä yk­kö­nen ja kak­ko­nen ovat seu­raa­vat:

1. Jo­ko L = ∅, tai jo­kai­sel­la σ ∈ Σ* on ole­mas­sa sel­lai­nen ρ ∈ Σ*, et­tä σρ ∈ L.
2. On ole­mas­sa DFA, jos­sa ei ole tur­hia ti­lo­ja, jon­ka ti­la­siir­ty­mä­funk­tio on täy­si, ja jo­ka hy­väk­syy L:n.

Jos yk­kö­nen pä­tee sik­si, et­tä L = ∅, niin kak­ko­nen pä­tee täs­tä syys­tä∅:n hy­väk­syy DFA, jos­sa on yk­si ti­la, se ei ole lop­pu­ti­la, ja sii­tä on jo­kai­sel­la mer­kil­lä kaa­ri it­seen­sä. Sen ti­la­siir­ty­mä­funk­tio on sel­väs­ti täy­si. Sii­nä ei ole tur­hia ti­lo­ja täs­tä syys­täAl­ku­ti­la ei kos­kaan ole tur­ha, ja mui­ta ti­lo­ja sii­nä ei ole...

Jos yk­kö­nen pä­tee mut­ta L ≠ ∅, niin kak­ko­nen pä­tee täs­tä syys­täAlus­sa ole­tet­tiin, et­tä jo­kin DFA hy­väk­syy L:n. Täs­tä syys­täLau­seen 1 no­jal­la on ole­mas­sa DFA, jos­sa ei ole tur­hia ti­lo­ja ja jo­ka hy­väk­syy L:n. To­dis­tam­me, et­tä sen ti­la­siir­ty­mä­funk­tio on täy­si.

Ol­koon q tä­män DFA:n mi­kä ta­han­sa ti­la. Täs­tä syys­täKos­ka tur­hia ti­lo­ja ei ole sii­hen pää­see al­ku­ti­las­ta jol­la­kin merk­ki­jo­nol­la σ. Ol­koon a mi­kä ta­han­sa merk­ki. Myös σa on merk­ki­jo­no eli σa ∈ Σ*. Täs­tä syys­täYk­kö­sen no­jal­la on ole­mas­sa sel­lai­nen ρ ∈ Σ*, et­tä σaρ ∈ L. Sik­si q:sta pää­see aρ:lla jo­hon­kin lop­pu­ti­laan. Täs­tä seu­raa, et­tä q:sta läh­tee a-ni­mi­nen kaa­ri. Siis δ(q, a) on mää­ri­tel­ty jo­kai­sel­la q ∈ Q ja a ∈ Σ..

Jos kak­ko­nen pä­tee, niin yk­kö­nen pä­tee täs­tä syys­täOte­taan tar­kas­te­luun mi­kä ta­han­sa σ ∈ Σ*. Kos­ka ti­la­siir­ty­mä­funk­tio on täy­si, al­ku­ti­las­ta pää­see σ:lla jo­hon­kin ti­laan. An­nam­me sen ni­mek­si q. Kos­ka tur­hia ti­lo­ja ei ole, jo­ko q:sta pää­see jo­hon­kin lop­pu­ti­laan tai q on al­ku­ti­la. Jos q:sta pää­see jo­hon­kin lop­pu­ti­laan, niin σρ ∈ L, mis­sä ρ on q:sta lop­pu­ti­laan vie­vän po­lun merk­kien muo­dos­ta­ma merk­ki­jo­no. Muus­sa ta­pauk­ses­sa q:sta ei pää­se mi­hin­kään lop­pu­ti­laan ja q on al­ku­ti­la. Täl­löin L = ∅..

Jol­lei DFA:n ti­la­siir­ty­mä­funk­tio ole täy­si, sii­tä saa­daan täy­si hy­väk­sy­tyn kie­len muut­tu­mat­ta li­sää­mäl­lä yk­si ti­la ja so­pi­vas­ti kaa­ria. Mi­ten kaa­ret li­sä­tään? vas­tausOl­koon li­sät­ty ti­la r. Se ei ole lop­pu­ti­la. Jo­kai­sel­le q ∈ Q ja a ∈ Σ, joil­le δ(q, a) ei ole mää­ri­tel­ty, li­sä­tään kaa­ri (q, a, r) eli ase­te­taan δ(q, a) = r. Li­säk­si jo­kai­sel­le a ∈ Σ li­sä­tään kaa­ri (r, a, r), jot­ta δ(r, a) oli­si mää­ri­tel­ty. Siis li­sä­tys­tä ti­las­ta läh­tee jo­kai­sel­la aak­ko­sel­la kaa­ri sii­hen it­seen­sä.

Lo­puk­si

DFA:ja käy­te­tään muun muas­sa merk­ki­jo­no­jen tun­nis­ta­mi­seen ja tie­to­lii­ken­ne­pro­to­kol­lien suun­nit­te­le­mi­seen. Ne ovat myös poh­ja muil­le hyö­dyl­li­sil­le for­ma­lis­meil­le, jois­ta tär­keim­piä ovat epä­de­ter­mi­nis­ti­set ää­rel­li­set au­to­maa­tit, sään­nöl­li­set lau­sek­keet ja yh­teys­riip­pu­mat­to­mat kie­li­opit.