Kysymysmuodot ensimmäiseen ja toiseen välikokeeseen.

Ensimmäisen välikokeen kysymysmuodot

1. Peruskysymykset 

- piirrä automaatti (deterministinen/epädeterministinen)

- muodosta säännöllinen ilmaus

- muodosta kontekstiton kielioppi

2. Edistyneemmät kysymykset

- muunna annettu epädeterministinen automaatti deterministiseksi

- muunna annettu deterministinen automaattui epädeterministiseksi

- 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ä kieli on säännöllinen/kontekstiton

- todista että operaatiot tuottaa säännöllisen/ kontekstittoman kielen jos argumenttikielet ovat säännöllisiä/kontekstittomia

- todista että operaatio ei tuota säännöllistä/kontekstittonta kieltä jos argumenttikielet ovat säännöllisiä/kontekstittomia

- jotain yleisiä todistuskysymyksiä...

Toisen kurssikokeen kysymysmuodot

1. Peruskysymykset

- piirrä pinoautomaatti annetulle kielelle

- piirrä Turing-kone annetulle kielelle

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

2. Edistyneemmät kysymykset

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

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

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

3. Syventävät kysymykset

- todista että kieli on (ei ole) kontekstiton

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

- 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

- todista että kieli kuuluu luokkaan P (tai NP)

Kokeessa luetellaan kaikki kappaleen 4 ja 5 lauseet, joita voit käyttää omien todistuksien osina vaikeiden kysymysten kohdalla. Lauseiden todistuksia ei kuitenkaan anneta luettavaksi kokeessa joten on suositeltavaa tutustua lauseiden todistuksiin koska usein niiden rakennetta voi käyttää hyväksi omissa todituksissa vaikeiden kysymysten kohdalla.

Below are question forms for the first and the second mid exam.

Forms of Questions for the first course exam

1. Basic questions

- Draw an automaton (deterministic or not)

- Form a regular expression

- Form a context-free grammar

2. More advanced questions

- Draw a deterministic automaton based on a nondeterministic automaton

- Draw a nondeterministic automaton based on a deterministic automaton

- Draw an automaton based on a regular expression

- Form a regular expression based on an automaton

3. Advanced question

- Prove that a language is not a regular

- Prove that a language is a regular /context-free

- Prove that some operations produce (or not) a regular/ a context-free language if the argument languages have the required properties

- some general proving questions...

Forms of Questions for the second course exam

1. Basic question

- Draw a PDA (deterministic or not) for a language

- Draw a TM (deterministic or not) for a language

- Draw a TM accomplishing a specific task with an input (for example, reverse the input string)

2. More advanced questions

- Draw a deterministic/non-deterministic PDA based on a context-free grammar (Lemma 2.21)

- Write a context-free grammar based on a PDA (Lemma 2.27)

- Analyze a given algorithm showing that the language belongs to P or NP class

3. Advanced questions

- Prove that a language is (or is not) a context-free

- Prove that some operations produce (or not) a context-free language if the argument languages are context-free

- Prove that some operations produce (or not produce) Turing-decidable language if the argument languages are Turing decidable

- Prove that some operations produce (or not produce) Turing-recognizable language if the argument languages are Turing recognizable

- Prove that a language is (or is not) Turing decidable

- Prove that a language is (or is not) Turing recognizable

- Prove that a language belongs to P (or NP) class

In the exam you are given all theorems from Chapter 4 and 5 and you can use those as your tools while constructing your answers to Advanced questions. However, the proofs of the theorems are not given, and, therefore, you are informed to study the proofs because they quite often gives you structural hints for your own proofs.