Alustavat hahmotelmat välikokeiden kysymysmuodoiksi

(kaikkia ei siis välttämättä kysytä ja vastaamisaika on  noin 90 minuuttiia)

Ensimmäisen välikokeen kysymysmuodot (1. välikoe ma 21.9. luentoaikana 14-16, sali A111)

1. Peruskysymykset 

- piirrä kielen A deterministinen tai epädeterministinen automaatti

-2. Edistyneemmät kysymykset

- muunna annettu epädeterministinen automaatti deterministiseksi automaatiksi

3. Syventävät kysymykset

- todista että operaatio (yhdiste, ketjutus, jne) tuottaa säännöllisen kielen jos argumenttikielet ovat säännöllisiä

Toisen välikokeen kysymysmuodot (2. välikoe ma 12.10 luentoaikana 14-16, sali A111)

1. Peruskysymykset 

- muodosta kielen A säännöllinen ilmaus

- muodosta kielen A kontekstiton kielioppi

2. Edistyneemmät kysymykset

- muunna annettu säännöllinen ilmaus automaatiksi

- muodosta automaatista säännöllinen ilmaus yleistetyn epädeterministisen automaatin avulla (GNF)

3. Syventävät kysymykset

- todista että kieli ei ole säännöllinen

- todista että operaatio (yhdiste, ketjutus, jne) tuottaa (ei tuota) kontekstittoman kielen jos argumenttikielet ovat kontekstittomia

Kolmannen välikokeen kysymysmuodot (3. välikoe ma 16.11 luentoaikana 14-16, sali A111)

1. Peruskysymykset

- piirrä pinoautomaatti annetulle kielelle

2. Edistyneemmät kysymykset

- käytä aputeoreemaa 2.21 ja piirrä pinoautomaatti annetun kieliopin perusteella

- käytä aputeoreemaa 2.27 ja muodosta kielioppi annetun pinoautomaatin perusteella

3. Syventävät kysymykset

- todista että kieli ei ole kontekstiton

- todista että operaatio tuottaa (tai ei tuota) kontekstittoman kielen jos lähtökielet ovat kontekstittomia

Neljännen välikokeen kysymysmuodot (4. välikoe ma 7.12 luentoaikana 14-16, sali A111)

1. Peruskysymykset

- piirrä Turing-kone annetulle kielelle

- piirrä Turing-kone joka tekee määritellyn tehtävän, esimerkiksi kääntää syötemerkkijononsa

2. Edistyneemmät kysymykset

- analysoi annettu algoritmi todistaen että kieliongelma kuuluu luokkaan P tai NP

3. Syventävät kysymykset

- todista että operaatio tuottaa (tai ei tuota) Turing-ratkeavan kielen jos lähtökielet ovat Turing-ratkeavia

- todista että operaatio tuottaa (tai ei tuota) Turing-tunnistettavan kielen jos lähtökielet ovat Turing-tunnistettavia

- todista että kieli on (tai ei ole) Turing-ratkeava

- todista että kieli on (tai ei ole) Turing-tunnistettava

Kokeessa luetellaan kaikki kappaleen 4 ja 5 teoreema, joita voit käyttää omien todistuksien osina syventävien kysymysten kohdalla. Teoreemojen todistuksia ei kuitenkaan anneta luettavaksi kokeessa joten on suositeltavaa tutustua teoreemojen todistuksiin koska usein niiden rakennetta voi käyttää hyväksi omissa todistuksissa syventävien kysymysten kohdalla.