Teh­tä­vä:
NFA:n muun­ta­mi­nen DFA:ksi

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

Täs­sä teh­tä­väs­sä ker­ra­taan epä­de­ter­mi­nis­tis­ten ää­rel­lis­ten au­to­maat­tien pe­rus­kä­sit­tei­tä ja muun­ne­taan epä­de­ter­mi­nis­ti­siä ää­rel­li­siä au­to­maat­te­ja de­ter­mi­nis­ti­sik­si. Teh­tä­vän DFA-pe­rus­asioi­ta tu­lee ol­la teh­ty, kos­ka siel­lä käy­dään lä­pi täl­le teh­tä­väl­le vält­tä­mät­tö­miä esi­tie­to­ja.

1. NFA:n mää­ri­tel­mä
2. Muun­nok­sen ma­te­ma­tiik­kaa
3. Muun­nos­har­joi­tuk­sia
4. Lo­puk­si

NFA:n mää­ri­tel­mä

NFA on siis muu­ten sa­man­lai­nen kuin DFA, mut­ta osit­tai­sen funk­tion δ pai­kal­la on re­laa­tio Δ. Sa­na ”re­laa­tio” tar­koit­taa mi­tä ta­han­sa jouk­koa A, jo­ka to­teut­taa eh­don muo­toa A ⊆ A₁ × … × A_n. Sen al­kiot esi­te­tään muo­dos­sa (a₁, …, a_n), ja pä­tee a₁ ∈ A₁, …, a_n ∈ A_n. Niin­pä il­maus Δ ⊆ Q × (Σ ∪ {ε}) × Q tar­koit­taa, et­tä Δ on jouk­ko kol­mi­koi­ta (q, a, q’), mis­sä (il­mai­se sa­nal­li­ses­ti) q on täl­lai­nenti­la olen­to, a on täl­lai­nenmerk­ki tai ε olen­to ja q’ on täl­lai­nenti­la olen­to. Ku­vas­sa (q, a, q’) piir­re­tään näinnuo­le­na, jo­ka al­kaa ti­las­ta q ja päät­tyy ti­laan q’, ja jon­ka var­rel­le a on kir­joi­tet­tu.

Kos­ka Δ on jouk­ko, hy­vin piir­re­tys­sä ku­vas­sa ei ole kah­ta kaar­ta, jot­ka …al­ka­vat sa­mas­ta ti­las­ta, ovat sa­man­ni­mi­set (mo­lem­pien var­rel­le on kir­joi­tet­tu sa­ma merk­ki tai mo­lem­pien var­rel­le on kir­joi­tet­tu ε), ja päät­ty­vät sa­maan ti­laan.. Jos Q = {1, 2} ja Σ = {a, b, c, d}, niin kaa­ria on vä­hin­tään näin mon­ta0 ja enin­tään näin mon­ta2 ⋅ (4 + 1) ⋅ 2 = 20.

Vaik­ka DFA:n δ on ta­pa­na esit­tää eri sym­bo­lil­la kuin NFA:n Δ, sil­le­kin pä­tee δ ⊆ Q × (Σ ∪ {ε}) × Q. DFA ei kui­ten­kaan ole sa­ma asia kuin NFA, kos­ka sil­le pä­te­vät nä­mä• Kaa­ren ni­me­nä ei voi ol­la ε.
• Sa­mas­ta ti­las­ta sa­mal­la ni­mel­lä läh­tee enin­tään yk­si kaa­ri. li­sä­ra­joi­tuk­set.

Niin­pä jo­kai­nen DFA on NFA. Täl­lai­nen sa­no­jen käyt­tö on hie­man omi­tuis­ta: se on sa­man­lais­ta kuin jos sa­not­tai­siin, et­tä jo­kai­nen epä­ai­to maa­laus on ai­to maa­laus. Täl­lai­sek­si sa­nas­to on kui­ten­kin va­kiin­tu­nut. Si­tä­pait­si ei­kös jo­kai­nen epä­luu­lo ole luu­lo? Suo­men­kie­li­kään ei siis ole täs­sä täy­sin joh­don­mu­kai­nen. Ma­te­ma­tii­kas­sa on muu­ta­kin sa­mal­la ta­val­la kum­mal­lis­ta kie­len­käyt­töä. Esi­mer­kik­si jo­kai­nen osit­tai­nen funk­tio on täy­si funk­tio.

Päin­vas­tai­nen ei pä­de: ei ole niin, et­tä jo­kai­nen NFA on DFA. Piir­rä mah­dol­li­sim­man pie­ni NFA, jo­ka ei ole DFA. vas­taus

Jo­kai­nen NFA, jos­sa on vain yk­si ti­la ja jon­ka kaar­ten ni­mis­sä ei esiin­ny ε, on DFA täs­tä syys­täSa­mas­ta ti­las­ta sa­mal­la ni­mel­lä läh­tee enin­tään yk­si kaa­ri, kos­ka mah­dol­li­sia kär­ki­pään ti­lo­ja on vain yk­si..

DFA:il­la q =σ⇒ q’ tar­koit­taa, et­tä on ole­mas­sa pol­ku q:sta q’:uun, jon­ka kaar­ten ni­met muo­dos­ta­vat merk­ki­jo­non σ. NFA:il­la ti­lan­ne on si­kä­li mo­ni­mut­kai­sem­pi, et­tä ε-kaa­ret ei­vät tuo­ta merk­ke­jä pol­kua vas­taa­vaan merk­ki­jo­noon. Esi­mer­kik­si ku­van NFA:lla pä­tee 1 =bbd⇒ 4 po­lun 1ε2b2b2ε3ε4d4 an­sios­ta. Po­lun pi­tuus voi siis ol­la suu­rem­pi kuin po­lun tuot­ta­man merk­ki­jo­non pi­tuus. Jat­koa var­ten an­nam­me ku­van NFA:lle ni­men a*b*c*. Se on myös ruu­dun oi­keas­sa ala­nur­kas­sa.

Se­kä DFA:n et­tä NFA:n ta­pauk­ses­sa σ kuu­luu au­to­maa­tin hy­väk­sy­mään kie­leen jos ja vain jos on ole­mas­sa al­ku­ti­las­ta jo­hon­kin lop­pu­ti­laan vie­vä pol­ku, jon­ka kaar­ten ni­mien jo­no ε:t pois jä­tet­ty­nä on σ. NFA:n hy­väk­sy­mä kie­li on siis {σ ∈ Σ* | ∃ q ∈ F: q̂ =σ⇒ q}. Sa­ma kaa­va pä­tee DFA:n hy­väk­sy­mäl­le kie­lel­le.

Ol­koon q ∈ F ja q₁ =ε⇒ q =ε⇒ q₂. Voi­ko hy­väk­syt­ty kie­li muut­tua, jos q₁ muu­te­taan lop­pu­ti­lak­si? vas­tausEi voi. Jo­kai­sel­la merk­ki­jo­nol­la σ, jol­la pää­see al­ku­ti­las­ta q₁:een, pää­see al­ku­ti­las­ta q:hun pol­kua q̂ =σ⇒ q₁ =ε⇒ q pit­kin. Se kuu­luu siis hy­väk­syt­tyyn kie­leen jo sil­loin kun q₁ ei vie­lä ole lop­pu­ti­la. Voi­ko hy­väk­syt­ty kie­li muut­tua, jos q₂ muu­te­taan lop­pu­ti­lak­si? vas­tausKyl­lä voi. Jos a*b*c*:ssä ti­la 4 muu­te­taan lop­pu­ti­lak­si, niin muun muas­sa d tu­lee uu­te­na hy­väk­syt­tyyn kie­leen.

Jos jo­kai­sel­le q ∈ Q pä­tee q̂ =ε⇒ q =ε⇒ q̂, niin mi­kä on hy­väk­syt­ty kie­li? vih­jeJos (q, a, q’) on mi­kä ta­han­sa kaa­ri, niin teh­tä­vän ole­tuk­sen mu­kaan q̂ =ε⇒ q ja q’ =ε⇒ q̂. Sik­si q̂ =a⇒ q̂. vas­tausJos F = ∅, niin myös hy­väk­syt­ty kie­li on ∅. Jos F ≠ ∅, niin kie­li on Γ*, mis­sä Γ on ku­vas­sa esiin­ty­vien kaar­ten ni­mien jouk­ko ε pois­lu­kien. pe­rus­te­lu 1Jo­kai­sel­le NFA:lle pä­tee, et­tä jos F = ∅, niin myös hy­väk­syt­ty kie­li on ∅. Jos lop­pu­ti­lo­ja ei ole, niin mi­kään pol­ku ei vie lop­pu­ti­laan, jo­ten mi­tään merk­ki­jo­noa ei hy­väk­sy­tä. pe­rus­te­lu 2Jos F ≠ ∅, niin on ole­mas­sa lop­pu­ti­la. An­nam­me sen ni­mek­si q_F. Teh­tä­vän ole­tuk­sen mu­kaan q̂ =ε⇒ q_F. Jo­kai­nen a₁a₂⋯a_n ∈ Γ* voi­daan hy­väk­syä po­lul­la, jo­ka vih­jeen mu­kaan kul­kee q̂ =a₁⇒ q̂ =a₂⇒ q̂ … q̂ =a_n⇒ q̂ =ε⇒ q_F. Vaik­ka voi­kin ol­la Σ ≠ Γ, mui­ta Σ*:n al­kioi­ta ei ole mu­ka­na seu­raa­vas­ta syys­tä. Jos merk­ki­jo­nos­sa esiin­tyy merk­ki, jol­la mi­kään kaa­ri ei ole mer­kit­ty, niin merk­ki­jo­non mu­kaan kul­ke­mi­nen epäon­nis­tuu vii­meis­tään sen koh­dal­la.

Pel­käs­tään ε-kaa­ris­ta muo­dos­tu­vat sil­mu­kat muo­dos­ta­vat eri­kois­ta­pauk­sen, jo­ka on otet­ta­va huo­mioon esi­mer­kik­si pump­paus­lem­maa kä­si­tel­täes­sä. Sel­lai­sen sil­mu­kan kier­tä­mi­nen tai kier­tä­mät­tä jät­tä­mi­nen ei muu­ta luet­tua merk­ki­jo­noa. Kaik­ki sil­mu­kan ti­lat voi­daan yh­dis­tää yh­dek­si ti­lak­si il­man, et­tä hy­väk­syt­ty kie­li muut­tuu. Tu­lee­ko tä­män yh­dis­te­tyn ti­lan ol­la lop­pu­ti­la? vas­tausYh­dis­te­tyn ti­lan tu­lee ol­la lop­pu­ti­la jos ja vain jos yk­si­kin sil­mu­kan ti­la on lop­pu­ti­la.

Muun­nok­sen ma­te­ma­tiik­kaa

Täs­sä lu­vus­sa ta­voit­tee­na on muun­taa NFA N = (Q_N, Σ, Δ, q̂_N, F_N) DFA:ksi D = (Q_D, Σ, δ, q̂_D, F_D), jo­ka hy­väk­syy sa­man kie­len. Tä­mä lu­ku ei eh­kä ole ihan help­po, jo­ten voit kat­soa sen suo­ri­te­tuk­si, jos koet op­pi­nee­si jo­tain uut­ta (ja tie­ten­kin myös jos sait sen teh­tyä). Pää­ta­voit­tee­na ei ole op­pia mi­ten muun­nos toi­mii, vaan mi­ten täl­lai­sia asioi­ta to­dis­te­taan. Sik­si to­dis­tus ete­nee huo­mat­ta­vas­ti pie­nem­min as­ke­lin kuin kir­jal­li­suu­des­sa on ta­pa­na, ja vä­lil­lä ker­ro­taan mik­si teh­dään niin kuin teh­dään.

Käy­täm­me ala­in­dek­se­jä _N ja _D osoit­ta­maan, kum­man au­to­maa­tin osis­ta kul­loin­kin pu­hum­me. Mo­lem­mil­la au­to­maa­teil­la on sa­ma aak­kos­to, jo­ten mer­kit­sem­me si­tä Σ em­me­kä Σ_D ja Σ_N. Sym­bo­lit Δ ja δ ei­vät tar­vit­se ala­in­dek­se­jä, kos­ka ne erot­tu­vat toi­sis­taan il­man­kin.

Tu­lok­se­na syn­ty­vän DFA:n D ti­lat ovat al­ku­pe­räi­sen NFA:n N ti­lo­jen jouk­ko­ja. Muun­nos on eh­kä hel­poin ym­mär­tää, jos jo­kai­sel­le σ ∈ Σ* otam­me käyt­töön mer­kin­nän q_σ tar­koit­ta­maan nii­den N:n ti­lo­jen jouk­koa, joi­hin N:n al­ku­ti­las­ta pää­see σ:lla N:n kaa­ria pit­kin.

q_σ = {q ∈ Q_N | q̂_N =σ⇒ q}

Muun­nok­sen tu­lok­sen osat voi­daan nyt il­mais­ta ly­hyil­lä kaa­voil­la. Nii­den si­säl­töä ava­taan kaa­vo­jen jäl­keen.

• Q_D = {q_σ | σ ∈ Σ*}
• Jos q_D ∈ Q_D ja a ∈ Σ, niin δ(q_D, a) =
  {q ∈ Q_N | ∃ q’ ∈ q_D: q’ =a⇒ q}.
• q̂_D = q_ε
• F_D = {q_σ | σ ∈ Σ* ∧ q_σ ∩ F_N ≠ ∅}

Merk­ki­jo­no­ja eli Σ*:n al­kioi­ta on ää­ret­tö­mäs­ti (pait­si jos Σ = ∅). Kaa­van Q_D = {q_σ | σ ∈ Σ*} voi aja­tel­la käy­vän lä­pi ne kaik­ki ja tuot­ta­van jo­kai­sel­le niis­tä ti­lan. Ti­lo­ja ei kui­ten­kaan syn­ny ää­ret­tö­mäs­ti täs­tä syys­täEri merk­ki­jo­noil­le voi syn­tyä sa­mo­ja ti­lo­ja, eli voi ol­la q_σ = q_ρ vaik­ka σ ≠ ρ.. Kos­ka tuo­tet­ta­vat ti­lat ovat Q_N:n …osa­jouk­ko­ja, nii­tä voi syn­tyä enin­tään näin mon­ta2^|Q_N|.

Ol­koon a merk­ki ja σ merk­ki­jo­no. Osan δ ym­mär­tä­mi­sek­si il­mai­sem­me q_σa:n seu­raa­vas­ti: q_σa on nii­den N:n ti­lo­jen jouk­ko, joi­hin pääs­tään q_σ:n si­säl­tä­mis­tä ti­lois­ta pol­kua pit­kin, jos­sa on en­sin nol­la tai useam­pia ε-kaa­ria, sit­ten yk­si a-kaa­ri, ja lo­puk­si nol­la tai useam­pia ε-kaa­ria.

q_σa = {q ∈ Q_N | ∃ q’ ∈ q_σ: q’ =a⇒ q}

Tä­män kaa­van to­dis­ta­mi­sek­si pi­tää osoit­taa, et­tä jos q ∈ q_σa, niin ∃ q’ ∈ q_σ: q’ =a⇒ q ja päin­vas­toin. To­dis­tus on yk­sin­ker­tai­nen ja tyl­sä. Sii­nä ve­do­taan tois­tu­vas­ti q_σ:n edel­lä ol­lee­seen mää­ri­tel­mään ja pa­ri ker­taa =a₁⋯a_n⇒:n mää­ri­tel­mään.

• Jos q ∈ q_σa, niin q_σ:n mää­ri­tel­män mu­kaan q̂_N =σa⇒ q eli N:n al­ku­ti­las­ta on pol­ku q:hun, jon­ka kaar­ten ni­mien jo­no ε:t pois jät­täen on σa. Tä­män po­lun vii­mei­nen muu kuin ε-kaa­ri on a-kaa­ri. Ol­koon q’ se ti­la, jos­ta tä­mä a-kaa­ri al­kaa. Ti­lal­le q’ pä­tee …q̂_N =σ⇒ q’ =a⇒ q. Sii­tä q_σ:n mää­ri­tel­mä tuot­taa …q’ ∈ q_σ. Niin­pä ∃ q’ ∈ q_σ: q’ =a⇒ q.
• Ole­te­taan ∃ q’ ∈ q_σ: q’ =a⇒ q. Sii­tä saa­daan q_σ:n mää­ri­tel­män avul­la …q̂_N =σ⇒ q’ ja vä­lit­tö­mäs­ti q’ =a⇒ q. Yh­des­sä niis­tä tu­lee …q̂_N =σ⇒ q’ =a⇒ q. To­dis­tus jat­kuu näinKun täs­tä po­lus­ta jä­te­tään q’ mai­nit­se­mat­ta, saa­daan q̂_N =σa⇒ q. ja näinSii­tä q_σ:n mää­ri­tel­mä tuot­taa q ∈ q_σa..

Ken­ties huo­ma­sit, et­tä juu­ri to­dis­ta­mam­me kaa­van oi­kea puo­li on mel­kein sa­man­lai­nen kuin δ(q_D, a):n mää­ri­tel­män oi­kea puo­li. Muu­ta eroa ei ole kuin (il­mai­se se­kä sym­bo­li­na et­tä sa­nal­li­ses­ti) sii­nä mis­sä δ(q_D, a):n mää­ri­tel­mäs­sä on tä­mäq_D eli tuo­tet­ta­van DFA:n ti­la, q_σa:n kaa­vas­sa on tä­mäq_σ eli nii­den ti­lo­jen jouk­ko, jo­hon al­ku­pe­räi­ses­sä NFA:ssa pää­see σ:lla. Niin­pä jos q_σ sat­tu­moi­sin on sel­lai­nen ti­la, jo­hon δ(q_D, a):n mää­ri­tel­mää voi so­vel­taa, niin saam­me δ(q_σ, a) = q_σa. Voi­ko näin tyy­li­käs tu­los ol­la sat­tu­maa? vas­tausVoi, mut­ta ai­ka usein ei ole. Täl­lä­kään ker­taa ei ole. Mer­kin­nät py­ri­tään usein va­lit­se­maan si­ten, et­tä mer­kin­tö­jen vä­li­set suh­teet vas­taa­vat mer­kin­tö­jen tar­koit­ta­mien asioi­den vä­li­siä suh­tei­ta. Se hel­pot­taa päät­te­lyn seu­raa­mis­ta.

Mit­kä q_σ ovat sel­lai­sia ti­lo­ja? Ti­lan q_σ saa pan­na q_D:n pai­kal­le δ(q_D, a):ssa sil­lä q_D:tä kos­ke­val­la eh­dol­la, mi­kä δ(q_D, a):n mää­ri­tel­mäs­sä on sa­not­tu. Se on tä­mäq_D ∈ Q_D. Täy­tyy siis ol­la q_σ ∈ Q_D.. Mit­kä q_σ to­teut­ta­vat tä­män eh­don? vih­jeSen nä­kee Q_D:n mää­ri­tel­mäs­tä. vas­tausKaik­ki.

Täs­tä seu­raa, et­tä jos va­lit­sem­me q̂_D:n so­pi­vas­ti, niin D:ssä jo­kai­sel­le merk­ki­jo­nol­le σ pä­tee q̂_D =σ⇒ q_σ. Se tar­koit­taa, et­tä aja­mal­la D:ssä σ:n saam­me sel­vil­le kaik­kien nii­den ti­lo­jen jou­kon, jois­sa N voi ol­la ajet­tuaan σ:n. Jot­ta tä­mä pä­ti­si kun σ = ε, täy­tyy ol­la …q̂_D =ε⇒ q_ε. Kos­ka DFA:is­sa ei ole ε-kaa­ria, on DFA:is­sa voi­mas­sa sään­tö, et­tä jos q =ε⇒ q’, niin …q’ = q. Ta­pauk­seen q̂_D =ε⇒ q_ε so­vel­let­tu­na tä­mä tar­koit­taa …q_ε = q̂_D. Juu­ri näin­hän edel­lä va­lit­tiin.

Olem­me lu­van­neet, et­tä q̂_D =σ⇒ q_σ, mut­ta em­me vie­lä ole to­dis­ta­neet si­tä. Nyt to­dis­tam­me. Ol­koon si­tä var­ten σ = a₁a₂⋯a_n mi­kä ta­han­sa merk­ki­jo­no. Tar­vit­sem­me seu­raa­vaa pe­riaa­tet­ta, jo­ta mer­kit­sem­me (*): jos DFA:ssa q =σ⇒ q’ ja δ(q’, a) = q’’, niin q =σa⇒ q’’. Pe­riaat­teen pä­te­vyys seu­raa suo­raan pe­rus­mää­ri­tel­mis­tä. Se on help­po näh­dä pä­te­väk­si, kun muo­toi­lee sen sa­noik­si: …Jos q:sta on σ:lla mer­kit­ty pol­ku q’:uun ja siel­tä on a-kaa­ri q’’:uun, niin yh­des­sä ne muo­dos­ta­vat σa:lla mer­ki­tyn po­lun q:sta q’’:uun..

• Kos­ka q̂_D =ε⇒ q̂_D ja q̂_D = q_ε, pä­tee (0) q̂_D =ε⇒ q_ε.
• Kos­ka δ(q_σ, a) = q_σa pä­tee jo­kai­sel­le merk­ki­jo­nol­le σ ja mer­kil­le a, saam­me δ(q_ε, a₁) = …q_εa1. Yh­des­sä (0):n ja (*):n kans­sa se tuot­taa …q̂_D =εa₁⇒ q_εa1. Kos­ka εa₁ = a₁, saam­me (1)q̂_D =a₁⇒ q_a1.
• Kos­ka δ(q_σ, a) = q_σa pä­tee jo­kai­sel­le merk­ki­jo­nol­le σ ja mer­kil­le a, saam­me …δ(q_a1, a₂) = q_a1a2. Yh­des­sä (1):n ja (*):n kans­sa se tuot­taa (2)q̂_D =a₁a₂⇒ q_a1a2.
• Kos­ka δ(q_σ, a) = q_σa pä­tee jo­kai­sel­le merk­ki­jo­nol­le σ ja mer­kil­le a, saam­me …δ(q_a1a2, a₃) = q_a1a2a3. Yh­des­sä (2):n ja (*):n kans­sa se tuot­taa (3)q̂_D =a₁a₂a₃⇒ q_a1a2a3.
• Tois­tu­mi­sen ylei­nen hah­mo vie (i)q̂_D =a₁⋯a_i⇒ q_a1⋯ai:stä (i + 1):een, ja se on seu­raa­va. Kos­ka δ(q_σ, a) = q_σa pä­tee jo­kai­sel­le merk­ki­jo­nol­le σ ja mer­kil­le a, saam­me …δ(q_a1⋯ai, a_i+1) = q_a1⋯ai+1. Yh­des­sä (i):n ja (*):n kans­sa se tuot­taa (i + 1)q̂_D =a₁⋯a_i+1⇒ q_a1⋯ai+1.

Tä­mä päät­te­ly ete­nee siis mi­tä ta­han­sa merk­ki­jo­noa pit­kin merk­ki ker­ral­laan, kun­nes ko­ko merk­ki­jo­no on sen pii­ris­sä. Niin­pä se to­dis­taa jo­kai­sel­le merk­ki­jo­nol­le σ, et­tä q̂_D =σ⇒ q_σ. Täl­lais­ta sa­man­lai­sil­la as­ke­lil­la pie­nes­tä suu­reen ete­ne­vää to­dis­tus­ta kut­su­taan …in­duk­tio­to­dis­tuk­sek­si.

Ha­lu­sim­me, et­tä D hy­väk­syy sa­man kie­len kuin N. Sik­si jos σ vie N:ssä al­ku­ti­las­ta jo­hon­kin lop­pu­ti­laan, pi­tää sa­man ta­pah­tua D:ssä, eli q_σ:n pi­tää ol­la lop­pu­ti­la. Jos σ ei vie N:ssä al­ku­ti­las­ta mi­hin­kään lop­pu­ti­laan, q_σ …ei saa ol­la lop­pu­ti­la. Mää­ri­tel­män­sä mu­kaan q_σ on nii­den N:n ti­lo­jen jouk­ko, joi­hin N:ssä pää­see N:n al­ku­ti­las­ta σ:lla. Sik­si on help­po kat­soa q_σ:sta, hy­väk­syy­kö N σ:n. Näin se käy.Kat­so­taan, si­säl­tää­kö q_σ yh­tään N:n lop­pu­ti­laa, eli pä­tee­kö q_σ ∩ F_N ≠ ∅. Edel­lä F_D mää­ri­tel­tiin D:n nii­den ti­lo­jen q_σ jouk­ko­na, joil­le tä­mä eh­to pä­tee. Ra­jaus D:n ti­loi­hin esi­tet­tiin näinRa­jau­dut­tiin nii­hin q_σ, joil­le σ on merk­ki­jo­no. Se on Q_D:n mää­ri­tel­män mu­kaan täs­mäl­leen sa­ma jouk­ko kuin Q_D:n ti­lo­jen jouk­ko..

Vie­lä ei ole ihan val­mis­ta. Em­me ole to­dis­ta­neet, et­tä D on DFA. Täl­lais­ten tar­kas­ta­mi­nen on usein help­poa ja saa­te­taan il­man mai­nin­taa jät­tää lu­ki­jan teh­tä­väk­si. Sii­nä on vaa­ra­na, et­tä lo­pul­ta ku­kaan ei tar­kas­ta asiaa, ja se ei pi­dä­kään paik­kaan­sa.

DFA:n mää­ri­tel­mäs­sä ase­te­taan jo­kai­sel­le osal­le oma eh­to. Mit­kä ne eh­dot ovat ja mit­kä niis­tä olem­me edel­lä jo tar­kas­ta­neet?  Q_DQ_D on ää­rel­li­nen jouk­ko. Tä­män olem­me tar­kas­ta­neet.  ΣΣ on ää­rel­li­nen jouk­ko, jol­le pä­tee ε ∉ Σ. Täs­tä em­me ole pu­hu­neet, mut­ta se on hy­vin il­mei­nen. Se ol­koon räs­ti 1.  δδ on osit­tai­nen funk­tio jou­kol­ta Q_D × Σ jou­kol­le Q_D. Tä­tä em­me ole tar­kas­ta­neet. Se on niin vai­kea, et­tä kan­nat­taa teh­dä muut en­sin ja teh­dä tä­mä lo­puk­si räs­tei­nä 3 ja 4.  q̂_Dq̂_D ∈ Q_D. Em­me eh­kä ole sa­no­neet tä­tä ai­van suo­raan, mut­ta se näh­dään hel­pos­ti to­dek­si. Tä­mä ol­koon räs­ti 2.  F_DF_D ⊆ Q_D. Edel­lä pe­rus­tel­tiin, et­tä F_D:n al­kiot ovat D:n ti­lo­ja.

Tar­kas­tam­me ne eh­dot, jot­ka ovat vie­lä tar­kas­ta­mat­ta. räs­ti 1Myös NFA:n mää­ri­tel­mäs­sä on sa­ma vaa­ti­mus, ja Σ on myös N:n aak­kos­to. Sik­si väi­te seu­raa sii­tä läh­tö­koh­das­tam­me, et­tä N on NFA. räs­ti 2Mää­ri­tel­tiin q̂_D = q_ε, q_ε on muo­toa q_σ, ja Q_D on kaik­kien si­tä muo­toa ole­vien ti­lo­jen jouk­ko. räs­ti 3Edel­lä δ(q_D, a) mää­ri­tel­tiin jo­kai­sel­le q_D ∈ Q_D ja a ∈ Σ, jo­ten δ on funk­tio niil­tä jou­koil­ta mil­tä pi­tää­kin. Se on it­se asias­sa täy­si funk­tio, mut­ta se ei hait­taa, sil­lä ma­te­ma­tii­kas­sa jo­kai­nen täy­si funk­tio on osit­tai­nen funk­tio. räs­ti 4Myös δ:n tu­lok­sen pi­tää ol­la Q_D:n al­kio. Tä­mä seu­raa sii­tä, et­tä jos q_D ∈ Q_D, niin Q_D:n mää­ri­tel­män vuok­si on ole­mas­sa jo­kin sel­lai­nen σ, et­tä q_D = q_σ. Olem­me osoit­ta­neet, et­tä δ(q_σ, a) = q_σa. Merk­ki­jo­non mää­ri­tel­mäs­tä seu­raa, et­tä jos σ ∈ Σ* ja a ∈ Σ, niin myös σa ∈ Σ*. Sik­si käyt­tä­mäl­lä Q_D:n mää­ri­tel­mäs­sä σa:ta näh­dään, et­tä δ:n tu­los eli q_σa on Q_D:n al­kio.

Tä­män lu­vun alus­sa lu­pa­sim­me, et­tä D on DFA ja hy­väk­syy sa­man kie­len kuin N. Olem­me osoit­ta­neet mo­lem­mat.

Muun­nos­har­joi­tuk­sia

Nyt har­joit­te­lem­me muun­nok­sen te­ke­mis­tä. En­sin muun­nam­me NFA:n a*b*c* de­ter­mi­nis­ti­sek­si. Vas­taus ra­ken­ne­taan al­la vä­hän ker­ras­saan. Voit mil­loin vain ha­lu­tes­sa­si tes­ta­ta vas­taus­ta­si täs­sä. Al­ku­ti­lan ni­mi on an­net­tu val­miik­si ja mui­den ti­lo­jen ni­met saat va­li­ta va­paas­ti isois­ta kir­jai­mis­ta (ei ääk­kö­siä). Esi­mer­kik­si A ::= "" | aC | bB tar­koit­taa, et­tä A on lop­pu­ti­la ja sii­tä on a-kaa­ri C:hen ja b-kaa­ri B:hen. Aak­kos­toa ei il­moi­te­ta. Va­li­tet­ta­vas­ti Math­Check ei vie­lä osaa tar­kas­taa, et­tä vas­tauk­se­si on DFA, jo­ten se hy­väk­syy myös vää­riä vas­tauk­sia.
ok_text Oi­kein! Täs­sä vie­lä ku­va: #<img src=#"http://users.jyu.fi/%7eava/DFA_abc.png#" alt=#"[a*b*c*:n hy­väk­sy­vän DFA:n ku­va]#"#> CFG_set A ::= aA | B | "" B ::= bB | C C ::= cC | dD | "" D ::= dD ; CFG_set2 A ::= ; CFG_compare
tai

Aak­kos­to on tä­mä{a, b, c, d}, ja sil­le ei ta­pah­du muun­nok­ses­sa mi­tään. Muo­dos­tam­me aluk­si ti­lan q̂_D, jo­ka tun­ne­taan myös täl­läq_ε merk­ki­jo­noa ala­in­dek­si­nä käyt­tä­väl­lä ni­mel­lä. Saam­me tu­lok­sek­si q̂_D = …{1, 2, 3, 4}.

Seu­raa­vak­si va­lit­sem­me sen q_D:ksi ja las­kem­me jo­kai­sel­le a ∈ Σ jou­kon {q ∈ Q_N | ∃ q’ ∈ q_D: q’ =a⇒ q}.

δ(q̂D, a) =	…{1, 2, 3, 4}
δ(q̂D, b) =	…{2, 3, 4}
δ(q̂D, c) =	…{3, 4}
δ(q̂D, d) =	…{4}

Saim­me yh­den van­han ti­lan eli {1, 2, 3, 4} ja kol­me uut­ta ti­laa. Kun teem­me jo­kai­sel­le uu­del­le ti­lal­le sa­man­lai­sen las­kun, löy­däm­me vie­lä yh­den uu­den ti­lan. Kaik­kiaan saam­me seu­raa­van tau­lu­kon:

	a	b	c	d
{1, 2, 3, 4}	…{1, 2, 3, 4}	…{2, 3, 4}	…{3, 4}	…{4}
{2, 3, 4}	…∅	…{2, 3, 4}	…{3, 4}	…{4}
{3, 4}	…∅	…∅	…{3, 4}	…{4}
{4}	…∅	…∅	…∅	…{4}
…∅	…∅	…∅	…∅	…∅

Lop­pu­ti­lo­ja ovat …{1, 2, 3, 4}, {2, 3, 4} ja {3, 4}. Piir­ret­ty­nä lop­pu­tu­los näyt­tää täl­tä Tyh­jää jouk­koa vas­taa­va ti­la on tur­ha. Sii­hen tu­le­vat kaa­ret oli­vat tyl­siä piir­tää, kos­ka ti­laa oli niu­kas­ti!.

Ohei­nen NFA hy­väk­syy täs­mäl­leen ne merk­ki­jo­not, jot­ka lop­pu­vat abaa. Muun­na se DFA:ksi. Lop­pu­tu­lok­sen ti­lat il­mais­tu­na NFA:n ti­lo­jen osa­jouk­koi­na ovat …{1}, {1, 2}, {1, 3}, {1, 2, 4} ja {1, 2, 5}. Piir­ret­ty­nä lop­pu­tu­los näyt­tää täl­tä.
ok_text Oi­kein! Täs­sä vie­lä ku­va: #<img src=#"http://users.jyu.fi/%7eava/DFA_lopussa_abaa.png#" alt=#"[a*b*c*:n hy­väk­sy­vän DFA:n ku­va]#"#> CFG_set A ::= aA | aB | bA B ::= bC C ::= aD D ::= aE E ::= "" ; CFG_set2 A ::= ; CFG_compare
tai

An­na NFA, jo­ka hy­väk­syy täs­mäl­leen ne merk­ki­jo­not, jot­ka lop­pu­vat abaa ja jois­sa abaa ei esiin­ny muual­la kuin lo­pus­sa. Esi­mer­kik­si A ::= aA | aB | C tar­koit­taa, et­tä A:sta on a-kaa­ri A:han, a-kaa­ri B:hen ja ε-kaa­ri C:hen.
ok_text Oi­kein! CFG_set A ::= aB | bA B ::= aB | bC C ::= aD | bA D ::= aE | bC E ::= "" ; CFG_set2 A ::= ; CFG_compare
tai

Lo­puk­si

DFA:il­le ja NFA:il­le voi­daan teh­dä mui­ta­kin temp­pu­ja. Voi­daan muun muas­sa yh­dis­tää kak­si NFA:ta yh­dek­si, jon­ka hy­väk­sy­mä kie­li on al­ku­pe­räis­ten NFA:iden hy­väk­sy­mien kiel­ten leik­kaus. DFA:il­la ja NFA:il­la on käy­tän­nön kan­nal­ta hyö­dyl­li­nen ka­ve­ri ni­mel­tä sään­nöl­li­set lau­sek­keet (regular expression), jo­ka on help­po muun­taa NFA:ksi.