Witam,
mam problem z narysowaniem czy zrobieniem maszyny turinga w jflab, chociaż wystarczy odpowiednie rozwiązanie, moje zadanie jest takie mam język
L = {0^n^2 | n>= 0}
i musze stworzyć maszyne turinga, ale jakoś mi nie działa.
Mam taką i nie wiem czemu nie działa. Może ktoś pomóc.
2? A od kiedy 2 jest potęgą? o_O Chyba że nie rozumiem tego języka który opisałeś. Chodzi o akceptowanie ciągów 0 których liczba jest kwadratem liczby naturalnej? A co dokładnie robi ta maszyna którą narysowałeś? Jaki algorytm stosuje? Na jakiej podstawie decydujesz czy liczba jest kwadratem czy nie?
Wydaje mi się że najłatwiejsza opcja to odejmowanie kolejnych liczb nieparzystych bo np. 25 = 1+3+5+7+9 i jest to prawda dla każdego kwadratu. Więc maszyna turinga mogłaby zamazywać najpierw 1, potem 3, potem 5, potem 7 symboli... i jeśli zamaże wszystko to akceptujemy, a jeśli nam brakło to odrzucamy.
Czyli np.:
A symbolizują tutaj elementy które chcemy usuwać z inputu, czyli 1, 3, 5, 7..., B symbolizują elementy już usunięte w tej turze. Przykład:
input: 000
Po przygotowaniu: 000|A
Taśma w kolejnych krokach algorytmu:
000|B
_00|B
_00|AAA
_00|BAA
__0|BAA
__0|BBA
___|BBA
___|BBB
i tutaj odrzucamy bo brakło nam symboli do usunięcia.
Analogicznie dla 0000:
Po przygotowaniu: 0000|A
Taśma w kolejnych krokach algorytmu:
0000|B
_000|B
_000|AAA
_000|BAA
__00|BAA
__00|BBA
___0|BBA
___0|BBB
____|BBB
I tutaj akceptujemy bo zdjęliśmy ostatni symbol inputu a jednocześnie nie mamy już żadnych A
Algorytm juz ci podałem, teraz rozpisz sobie tablicę przejść a potem ja namaluj i tyle. Ale tych stanów tam będzie dość sporo, chyba że istnieje jakis dużo łatwiejszy algorytm?
Na szybko:
| stan | symbol czytany | symbol pisany | kierunek | nowy stan |
|---|---|---|---|---|
| p1 | 0 | 0 | -> | p1 |
| p1 | _ | $ | -> | p2 |
| p2 | _ | A | <- | r1 |
| r1 | $ | $ | <- | r1 |
| r1 | 0 | 0 | <- | r1 |
| r1 | _ | _ | -> | s1 |
| s1 | 0 | 0 | -> | s1 |
| s1 | $ | $ | -> | s1 |
| s1 | B | B | -> | s1 |
| s1 | A | B | <- | r2 |
| s1 | _ | _ | <- | c1 |
| c1 | B | B | <- | c1 |
| c1 | $ | $ | <- | c1 |
| c1 | _ | ACCEPT | ||
| c1 | 0 | 0 | -> | a1 |
| a1 | $ | $ | -> | a1 |
| a1 | B | B | -> | a1 |
| a1 | B | A | -> | a1 |
| a1 | _ | A | -> | a2 |
| a2 | _ | A | <- | r1 |
| r2 | B | B | <- | r2 |
| r2 | A | A | <- | r2 |
| r2 | $ | $ | <- | r2 |
| r2 | 0 | 0 | <- | r2 |
| r2 | _ | _ | -> | s2 |
| s2 | 0 | _ | -> | s1 |
| s2 | $ | REJECT |
p1,p2 to ten preprocessing, gdzie idziemy na koniec, stawiamy sobie $ za inputem a potem stawiamy sobie A na końcu
s1,s2 to główna pętla algorytmu, s1 oznacza że idziemy na koniec i zamieniamy jedno A na B, s2 oznacza że idziemy w prawo i zamieniamy jedno 0 na blanka
r1,r2 to wracanie na początek inputu (r1 po preprocessingu a r2 w głównej pętli algorytmu)
a1,a2 są zeby dodać na końcu kolejne dwa A na obiegu pętli
c1 to sprawdzenie czy akceptujemy (tzn jeśli nie znaleźliśmy kolejnego A do zamiany na B sprawdzamy czy po lewej od $ jest juz tlyko blank czy jescze jakieś 0)
@Shalom: Czy mógłbyś sprawdzić czy dobrze zrobiłam bo cos mi nie łapie 4 i powyżej
coś mniej więcej w tym momencice
a1 _ A -> a2
a2 _ A <- r1
r2 B B <- r2
r2 A A <- r2
r2 $ $ <- r2
r2 0 0 <- r2
r2 _ _ -> s2
s2 0 _ -> s1
s2 $ REJECT
@Shalom: Hej jakby to wyglądało na wieloszynowej maszynie turinga?? Bo znowu mam z tym problem..
No ale tu nie ma jednego poprawnego algorytmu. Możesz napisać co sobie chcesz. Np. w tym algorytmie który podawałem wyżej trzeba było kombinować z tymi dodatkowymi symbolami pisanymi na końcu, a tutaj mozesz je pisać na innej taśmie zamiast jeździć wte i wewte co chwila. Czyli te moje A i B trzymasz na drugiej taśmie i już.
Ale chcesz jakieś formalne wyliczenia? Na oko będzie n*(2*n+logn) gdzie n to długość inputu, bo usunięcie jednego symbolu (których jest n) kosztuje nas dwa przejścia po całej taśmie (2n), plus na końcu powoli rośnie nam jeszcze ten fragment z A/B który będzie miał jakieś logn długości.
Nie wiem co tu można jaśniej opisać. Algorytm działa tak, ze "usuwa" z wejscia po 1 symbolu, a symboli jest n. Usuniecie jednego symbolu wymaga przejechania głowicą na koniec taśmy a potem znów na początek, czyli przelatujemy 2*n pozycji, plus jeszcze na końcu taśmy dopisujemy sobie te 1,3,5,7... więc taśma co 3 ruchy będzie dłuższa o 2 symbole, więc dorzucamy tam jakiś logn. Więc dla 1 symbolu potrzeba 2*n+logn a dla n symboli n*(2*n+logn)
