[Maszyna Turinga] Akceptacja parzystej liczby

jerer
Użytkownik
Użytkownik
Posty: 57
Rejestracja: 29 maja 2008, o 22:09
Płeć: Mężczyzna
Podziękował: 16 razy

[Maszyna Turinga] Akceptacja parzystej liczby

Post autor: jerer »

Witam. mam takie zadanie i nie wiem jak je zrobić.

Mamy dany alfabet \(\displaystyle{ \Sigma= \{\#,1\}}\), oraz słowo na taśmie składające się z \(\displaystyle{ n}\) jedynek ograniczony z obu stron symbolami #. Skonstruuj deterministyczną maszynę Turinga która odpowie TAK, jeżeli n będzie parzyste i NIE w przeciwnym wypadku. Załóż, że głowica w stanie początkowym jest umieszczona na pierwszej od lewej strony jedynce.


z góry dziękuje za pomoc
Ostatnio zmieniony 5 lip 2012, o 18:01 przez Afish, łącznie zmieniany 2 razy.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Całe wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

[Maszyna Turinga] Akceptacja parzystej liczby

Post autor: Zordon »

Dwa stany, jeden dla parzystej drugi dla nieparzystej długości przeskakujące na zmianę. Reszta zależy od szczegółów definicji maszyny Turinga.
ODPOWIEDZ