Tehtävä:
Pikkukysymyksiä äärellisistä automaateista

Tässä tehtävässä kerrataan äärellisiin auto­maatteihin liittyviä perus­käsitteitä pienten kyllä / ei -kysymysten avulla.

Koska luonnol­linen kieli on usein moni­tulkin­taista, joidenkin väitteiden tarkka merkitys on ilmaistu myös kaavana. Kaavat kannattaa lukea ja miettiä silloinkin kun sanallinen väite on selvä, jotta kaava­kieli tulisi tutuksi. Kaava­kielen yleiset piirteet on kuvattu yksityis­kohtaisesti täällä (aukeaa uuteen väli­lehteen) luvuissa ”Propositio­logiikka” ja ”Predikaatti­logiikka”. D, D₁ jne. edustavat DFA:ita; N, N₁ jne. edustavat NFA:ita; ja σ, ρ jne. edustavat äärellisiä merkki­jonoja.

Valitse jokaiselle DFA:lle D = (Q, Σ, δ, q̂, F) paikkansa pitävät väitteet. verbose_off only_no_yes_on ok_text Teit oikeat valinnat! /*Mikä tahansa tila voi olla loppu­tila tai epä­loppu­tila. Tämä koskee myös alku­tilaa. DFA:ssa voi olla loppu­tiloja, joihin ei ole polkua alku­tilasta.*/ only_no_yes_on hide_expr 1 = hide_expr 0

	Jokainen tila on alku­tila tai loppu­tila. ∀ q ∈ Q: q = q̂ ∨ q ∈ F
	Mikään tila ei ole sekä alku­tila että loppu­tila. ∀ q ∈ Q: ¬(q = q̂ ∧ q ∈ F)
	Jos loppu­tiloja ei ole, niin hyväksytty kieli on tyhjä. F = ∅  ⇒  L(D) = ∅
	Jos hyväksytty kieli on tyhjä, niin loppu­tiloja ei ole. L(D) = ∅  ⇒  F = ∅

tai

Valitse paikkansa pitävät väitteet. verbose_off only_no_yes_on ok_text Teit oikeat valinnat! /*Jokainen DFA hyväksyy täsmälleen yhden kielen. Hyväk­sytty kieli voi olla ääretön tai mitä tahansa äärel­listä kokoa.*/ only_no_yes_on hide_expr 5 = hide_expr 0

	On olemassa DFA, joka hyväksyy nolla merkki­jonoa. ∃ D: |L(D)| = 0
	On olemassa DFA, joka hyväksyy täsmälleen yhden merkki­jonon. ∃ D: |L(D)| = 1
	On olemassa DFA, joka hyväksyy useamman kuin yhden merkki­jonon mutta silti vain äärellisen määrän. ∃ D: 1 < |L(D)| < ∞
	On olemassa DFA, joka hyväksyy ääret­tömän monta merkki­jonoa. ∃ D: |L(D)| = ∞
	On olemassa DFA, joka hyväksyy nolla kieltä.
	On olemassa DFA, joka hyväksyy täsmälleen yhden kielen.
	On olemassa DFA, joka hyväksyy useamman kuin yhden kielen mutta silti vain äärellisen määrän.
	On olemassa DFA, joka hyväksyy ääret­tömän monta kieltä.

tai

Valitse paikkansa pitävät väitteet. verbose_off only_no_yes_on ok_text Teit oikeat valinnat! /*Kolmas kohta ei päde, koska voi olla, että kumpikaan DFA ei hyväksy yhtään merkki­jonoa.*/ only_no_yes_on hide_expr 3 = hide_expr 0

	Jos kaksi DFA:ta hyväksyy saman merkki­jonon, niin ne hyväk­syvät saman kielen. σ ∈ L(D1) ∧ σ ∈ L(D2)  ⇒  L(D1) = L(D2)
	Jos kaksi DFA:ta hyväksyy samat merkki­jonot, niin ne hyväk­syvät saman kielen. ∀ σ: σ ∈ L(D1) ↔ σ ∈ L(D2)  ⇒  L(D1) = L(D2)
	Jos kaksi DFA:ta hyväksyy saman kielen, niin ne hyväk­syvät saman merkki­jonon. L(D1) = L(D2)  ⇒  ∃ σ: σ ∈ L(D1) ∧ σ ∈ L(D2)
	Jos kaksi DFA:ta hyväksyy saman kielen, niin ne hyväk­syvät samat merkki­jonot. L(D1) = L(D2)  ⇒  ∀ σ: σ ∈ L(D1) ↔ σ ∈ L(D2)
	Jos kaksi DFA:ta hyväksyy eri kielet, niin ne eivät ole sama DFA. L(D1) ≠ L(D2)  ⇒  D1 ≠ D2
	Eri DFA:t hyväk­syvät eri kielet. D1 ≠ D2  ⇒  L(D1) ≠ L(D2)

tai

Valitse paikkansa pitävät väitteet. verbose_off only_no_yes_on ok_text Teit oikeat valinnat! /*Väitteistä neljä pätee.*/ only_no_yes_on hide_expr 4 = hide_expr 0

	Sama DFA voi hyväksyä monta eri merkki­jonoa. ∃ D: ∃ σ ∈ L(D): ∃ ρ L(D): σ ≠ ρ
	Monta eri DFA:ta voi hyväksyä saman merkki­jonon. ∃ σ: ∃ D1: ∃ D2: σ ∈ L(D1) ∧ σ ∈ L(D2)
	Sama DFA voi hyväksyä saman merkki­jonon monella eri loppu­tilalla.
	Sama DFA voi hyväksyä monta eri merkki­jonoa samalla loppu­tilalla.
	On olemassa merkki­jono, jota mikään DFA ei hyväksy. ∃ σ: ∀ D: σ ∉ L(D)
	On olemassa DFA, joka ei hyväksy mitään merkki­jonoa. ∃ D: ∀ σ: σ ∉ L(D)

tai

Valitse paikkansa pitävät väitteet. verbose_off only_no_yes_on ok_text Teit oikeat valinnat! /*Yhdellä väitteistä on eri totuusarvo kuin edellisessä kohdassa.*/ only_no_yes_on hide_expr 5 = hide_expr 0

	Sama NFA voi hyväksyä monta eri merkki­jonoa.
	Monta eri NFA:ta voi hyväksyä saman merkki­jonon.
	Sama NFA voi hyväksyä saman merkki­jonon monella eri loppu­tilalla.
	Sama NFA voi hyväksyä monta eri merkki­jonoa samalla loppu­tilalla.
	On olemassa merkki­jono, jota mikään NFA ei hyväksy.
	On olemassa NFA, joka ei hyväksy mitään merkki­jonoa.

tai

Syötteenä on NFA ja tavoit­teena on NFA, jonka hyväk­symä kieli on syöte-NFA:n hyväk­symät merkki­jonot takaperin. Valitse todet väittämät ja ne toimen­piteet, joilla tavoite-NFA saadaan aikaan. Valitse toimen­pide myös siinä tapauk­sessa, että se on tarpeen osalle syöte-NFA:ista ja osalle ei. Jos toimen­piteestä ei ole koskaan hyötyä niin jätä se valitse­matta siinäkin tapauk­sessa, että siitä ei olisi koskaan haittaakaan. verbose_off only_no_yes_on ok_text Teit oikeat valinnat! /*NFA:lla on aina täsmälleen yksi alku­tila, mutta loppu­tilojen määrä voi olla mikä vain. Niinpä, jos loppu­tilojen määrä ei ole yksi, ei voida muuttaa jokaista loppu­tilaa alku­tilaksi. Siksi lisätään uusi tila, josta tehdään alku­tila ja josta vedetään ε-kaaret alku­peräisiin loppu­tiloihin. Jos alku­peräinen alku­tila on myös loppu­tila, sitä ei muuteta epäloppu­tilaksi.*/ only_no_yes_on hide_expr 3 = hide_expr 0

	Turhat tilat poistetaan.
	Kaaret käännetään takaperin.
	Lisätään yksi tila ja jokin määrä ε-kaaria.
	Jokaisesta alku­peräisestä loppu­tilasta tehdään alku­tila.
	Jokaisesta alku­peräisestä alku­tilasta tehdään loppu­tila.
	Jokainen alku­peräinen loppu­tila muu­tetaan epäloppu­tilaksi.

tai

Valitse todet väittämät koskien edellisen tehtävän algo­ritmia. Parannettu algo­ritmi tarkoittaa muun­nosta, jossa, silloin kun mahdol­lista, ei lisätä uutta tilaa vaan muutetaan alku­peräiset loppu­tilat alku­tiloiksi. verbose_off only_no_yes_on ok_text Teit oikeat valinnat! only_no_yes_on hide_expr 4 = hide_expr 0

	Jos syöte on DFA, niin myös loppu­tulos on DFA.
	Jos syöte ei ole DFA, niin loppu­tulos ei ole DFA.
	Jos syötteessä on turhia tiloja, niin loppu­tuloksessakin on turhia tiloja.
	Jos syötteessä ei ole turhia tiloja, niin loppu­tuloksessakaan ei ole turhia tiloja.
	Kun parannettu algo­ritmi suori­tetaan kahdesti peräkkäin, tulos on alku­peräinen syöte-NFA.
	Kun parannettu algo­ritmi suori­tetaan kolmesti peräkkäin, saadaan sama tulos kuin suorit­tamalla se vain yhdesti.
	Kun parannettu algo­ritmi suori­tetaan neljästi peräkkäin, saadaan sama tulos kuin suorit­tamalla se kahdesti.

tai