Formaalit kielet ja automaattien teoria / syksy 2008

Harjoitus 6, viikko 42

1. Konstruoi Turingin kone, jossa luku/kirjoituspää liikkuu oikealle, kunnes se löytää kaksi peräkkäistä a:ta ja pysähtyy heti sen jälkeen. Aakkostona on {a, b}.

2. Konstruoi yksityiskohtaisesti Turingin koneet LL ja RRR.

3. Esitä luennolla esitetyn ”kopiointikoneen” lasku vaiheittain, kun syöttönauhalla on ensimmäisen ruudun (kolmio) jälkeen yksi tyhjä ja sitten sana aabb. Luku/kirjoituspää on alkutilanteessa tyhjän ruudun (toisen ruudun) kohdalla.

4. Esitä luennolla esitetyn ”oikelle siirtävän koneen, right-shifting machine” lasku vaiheittain, kun syöttönauhalla on ensimmäisen ruudun (kolmio) jälkeen yksi tyhjä ja sitten sana aabb. Luku/kirjoituspää on alkutilanteessa sanan aabb jälkeisen tyhjän ruudun kohdalla.

5. Konstruoi Turingin kone, joka ratkaisee seuraavat aakkoston {a, b} kielet:

{e}, {a}, {a}*.

6. Konstruoi Turingin kone, joka ratkaisee seuraavat kielen a*ba*b.