Vihjeitä harjoitustehtäviin

Lama-s06, 9.2

Kannattaa huomata, että tässä tehtävässä kaivataan nimenomaan yksinauhaista determinististä Turingin konetta.

Jonkinlainen yleinen resepti tämäntyyppisiin tehtäviin, joissa pitää esittää tietyn kielen tunnistava Turingin kone:

Siirrytään nyt enemmän kohti spoilereita. Jatkoa ei kannata lukea ennen kuin on itse yrittänyt ratkaista tehtäviä. Joka kohdassa kehitellään ideaa useammassa vaiheessa; jos et pääse alkuun, voit lukea muutaman ensimmäisen kohdan, ja yrittää sitten itse eteenpäin.

9.2 (a): Sovelletaan tuota ylläolevaa reseptiä.

9.2 (b):

9.2 (c):