Maszyna Turinga - Listy od czytelników

Czas:  2007-01-13 20:16:53
Tytuł: Maszyna Turinga
Od:    ekonovember
Temat: Algorytm na maszynę

Witam, przesyłam algorytm na maszynę - do zadania, które występuje często na egzaminie ze wstępu do informatyki (WDI). Treść zadania:

Dla alfabetu <a, b, c> zdefiniować maszynę Turinga, która nie dopuści do wystąpienia na wyjściu kombinacji symboli "ba" obok siebie z dowolnej długości skowa.

Przesyłam moja realizacje problemu, pomijam algorytm słowny, przysyłam od razu implementacje na symulator z Pana strony, mam nadzieje, że będzie przydatny

Program
#,q0,K,q0,L a,q0,a,q0,R b,q0,b,q1,R c,q0,c,q0,R #,q1,K,q1,L a,q1,#,q2,L b,q1,b,q1,R c,q1,c,q0,R b,q2,#,q3,R #,q3,#,q4,R #,q4,#,q12,L a,q4,#,q5,L b,q4,#,q7,L c,q4,#,q9,L #,q5,#,q6,L #,q6,a,q11,R #,q7,#,q8,L #,q8,b,q11,R #,q9,#,q10,L #,q10,c,q11,R #,q11,#,q3,R #,q12,#,q12,L a,q12,a,q13,L b,q12,b,q13,L c,q12,c,q13,L #,q13,#,q0,R a,q13,a,q13,L b,q13,b,q13,L c,q13,c,q13,L

Program

#,q0,K,q0,L
a,q0,a,q0,R
b,q0,b,q1,R
c,q0,c,q0,R
#,q1,K,q1,L
a,q1,#,q2,L
b,q1,b,q1,R
c,q1,c,q0,R
b,q2,#,q3,R
#,q3,#,q4,R
#,q4,#,q12,L
a,q4,#,q5,L
b,q4,#,q7,L
c,q4,#,q9,L
#,q5,#,q6,L
#,q6,a,q11,R
#,q7,#,q8,L
#,q8,b,q11,R
#,q9,#,q10,L
#,q10,c,q11,R
#,q11,#,q3,R
#,q12,#,q12,L
a,q12,a,q13,L
b,q12,b,q13,L
c,q12,c,q13,L
#,q13,#,q0,R
a,q13,a,q13,L
b,q13,b,q13,L
c,q13,c,q13,L

Jeszcze jeden algorytm może być przydatny, odejmowanie jedynek zapisanych w formacie #1111-111 - algorytm zwraca ciąg jedynek odpowiadający wynikowi, dodatkowo ustala znak wyniku +, -, w przypadku wyzerowania zwraca 0.

Program
1,q0,#,q1,R -,q0,-,q5,R #,q1,#,q2,L 0,q1,0,q1,R 1,q1,1,q1,R +,q1,+,q1,R -,q1,-,q1,R 1,q2,#,q3,L -,q2,#,q4,L #,q3,#,q0,R 0,q3,0,q3,L 1,q3,1,q3,L +,q3,+,q3,L -,q3,-,q3,L #,q4,1,q6,L 0,q4,0,q4,L 1,q4,1,q4,L +,q4,+,q4,L -,q4,-,q4,L #,q5,#,q6,L -,q6,0,q0,L #,q6,+,q0,L

Program

1,q0,#,q1,R
-,q0,-,q5,R
#,q1,#,q2,L
0,q1,0,q1,R
1,q1,1,q1,R
+,q1,+,q1,R
-,q1,-,q1,R
1,q2,#,q3,L
-,q2,#,q4,L
#,q3,#,q0,R
0,q3,0,q3,L
1,q3,1,q3,L
+,q3,+,q3,L
-,q3,-,q3,L
#,q4,1,q6,L
0,q4,0,q4,L
1,q4,1,q4,L
+,q4,+,q4,L
-,q4,-,q4,L
#,q5,#,q6,L
-,q6,0,q0,L
#,q6,+,q0,L

Program odbijający lustrzanie liczbę binarną po jej prawej stronie.

"-" znak wypełnienia taśmy

Przykład:

przed

--1011---

--10111101--

Program
-,q0,-,q0,R 0,q0,0,q1,R 1,q0,1,q1,R 1,q1,1,q1,R 0,q1,0,q1,R -,q1,-,q2,L //jesteśmy na ost elemencie -,q2,-,q88,R 1,q2,,q3,R //odczytano 1 - zaznaczenie symbolem miejsca powrotu 0,q2,,q33,R //odczytano 0 - zaznaczenie symbolem miejsca powrotu 1,q3,1,q3,R 0,q3,0,q3,R //przejście na pierwsze wolne miejsce -,q3,1,q4,R //wpisanie wczytanej cyfry -,q4,-,q4,L //powrót 1,q4,1,q4,L 0,q4,0,q4,L ,q4,1,q2,L 1,q33,1,q33,R 0,q33,0,q33,R //przejście na pierwsze wolne miejsce -,q33,0,q44,R //wpisanie wczytanej cyfry -,q44,-,q44,L //powrót 1,q44,1,q44,L 0,q44,0,q44,L ,q44,0,q2,L

Program

-,q0,-,q0,R
0,q0,0,q1,R
1,q0,1,q1,R
1,q1,1,q1,R
0,q1,0,q1,R
-,q1,-,q2,L   //jesteśmy na ost elemencie -,q2,-,q88,R
1,q2,*,q3,R   //odczytano 1 - zaznaczenie symbolem * miejsca powrotu
0,q2,*,q33,R  //odczytano 0 - zaznaczenie symbolem * miejsca powrotu
1,q3,1,q3,R
0,q3,0,q3,R   //przejście na pierwsze wolne miejsce
-,q3,1,q4,R   //wpisanie wczytanej cyfry
-,q4,-,q4,L   //powrót
1,q4,1,q4,L
0,q4,0,q4,L
*,q4,1,q2,L
1,q33,1,q33,R
0,q33,0,q33,R //przejście na pierwsze wolne miejsce
-,q33,0,q44,R //wpisanie wczytanej cyfry
-,q44,-,q44,L //powrót
1,q44,1,q44,L
0,q44,0,q44,L
*,q44,0,q2,L

Program sprawdzający, czy podany wyraz składający się z symboli {a,b,c} jest palindromem, tj czy czytany od końca do początku jest taki sam jak czytany od początku do końca,

Jako wypełnienie taśmy przyjąć znak myślnika "-"

Poprawny wyraz po sprawdzeniu pozostawia na taśmie symbol '1', a wyraz niepoprawny kończy się w stanie q99

Poprawny wpis na taśmę

-abbcbba

-cbaabc

-abcbba - ten wyraz nie jest palindromem

Program
-,q0,-,q0a,R -,q0a,1,q88,R //znaleziono a,q0a,-,q1a,R //znaleziono a b,q0a,-,q11a,R //znaleziono b c,q0a,-,q111a,R //znaleziono b a,q0,-,q1a,R //znaleziono a b,q0,-,q11a,R //znaleziono b c,q0,-,q111a,R //znaleziono c -,q1a,1,q88,R //pojedynczy palindrom - ok a,q1a,a,q1,R b,q1a,b,q1,R c,q1a,c,q1,R a,q1,a,q1,R b,q1,b,q1,R c,q1,c,q1,R -,q1,-,q2,L //koniec wyrazu, cofnij na poprzednie b,q2,b,q99,R //źle c,q2,c,q99,R //źle a,q2,-,q3,L //ok a,q3,a,q3,L b,q3,b,q3,L c,q3,c,q3,L -,q3,-,q0,R -,q11a,1,q88,R //pojedynczy palindrom - ok a,q11a,a,q11,R b,q11a,b,q11,R c,q11a,c,q11,R a,q11,a,q11,R b,q11,b,q11,R c,q11,c,q11,R -,q11,-,q22,L //koniec wyrazu, cofnij na poprzednie a,q22,a,q99,R //źle c,q22,c,q99,R //źle b,q22,-,q33,L //ok a,q33,a,q33,L b,q33,b,q33,L c,q33,c,q33,L -,q33,-,q0,R -,q111a,1,q88,R //pojedynczy palindrom - ok a,q111a,a,q111,R b,q111a,b,q111,R c,q111a,c,q111,R a,q111,a,q111,R b,q111,b,q111,R c,q111,c,q111,R -,q111,-,q222,L //koniec wyrazu, cofnij na poprzednie a,q222,a,q99,R //źle b,q222,b,q99,R //źle c,q222,-,q3,L //ok a,q333,a,q333,L b,q333,b,q333,L c,q333,c,q333,L -,q333,-,q0,R

Program

-,q0,-,q0a,R
-,q0a,1,q88,R   //znaleziono
a,q0a,-,q1a,R   //znaleziono a
b,q0a,-,q11a,R  //znaleziono b
c,q0a,-,q111a,R //znaleziono b
a,q0,-,q1a,R    //znaleziono a
b,q0,-,q11a,R   //znaleziono b
c,q0,-,q111a,R  //znaleziono c
-,q1a,1,q88,R   //pojedynczy palindrom - ok
a,q1a,a,q1,R
b,q1a,b,q1,R
c,q1a,c,q1,R
a,q1,a,q1,R
b,q1,b,q1,R
c,q1,c,q1,R
-,q1,-,q2,L     //koniec wyrazu, cofnij na poprzednie
b,q2,b,q99,R    //źle
c,q2,c,q99,R    //źle
a,q2,-,q3,L     //ok
a,q3,a,q3,L
b,q3,b,q3,L
c,q3,c,q3,L
-,q3,-,q0,R
-,q11a,1,q88,R   //pojedynczy palindrom - ok
a,q11a,a,q11,R
b,q11a,b,q11,R
c,q11a,c,q11,R
a,q11,a,q11,R
b,q11,b,q11,R
c,q11,c,q11,R
-,q11,-,q22,L    //koniec wyrazu, cofnij na poprzednie
a,q22,a,q99,R    //źle
c,q22,c,q99,R    //źle
b,q22,-,q33,L    //ok
a,q33,a,q33,L
b,q33,b,q33,L
c,q33,c,q33,L
-,q33,-,q0,R
-,q111a,1,q88,R   //pojedynczy palindrom - ok
a,q111a,a,q111,R
b,q111a,b,q111,R
c,q111a,c,q111,R
a,q111,a,q111,R
b,q111,b,q111,R
c,q111,c,q111,R
-,q111,-,q222,L   //koniec wyrazu, cofnij na poprzednie
a,q222,a,q99,R    //źle
b,q222,b,q99,R    //źle
c,q222,-,q3,L     //ok
a,q333,a,q333,L
b,q333,b,q333,L
c,q333,c,q333,L
-,q333,-,q0,R

PS. świetny symulator, pozdrawiam

Piotr Krzynowek

Czas:  2009-05-25 21:02:05
Tytuł: Maszyna Turinga - Symulator maszyny Turinga
Od:    Piotr Wittchen
Temat: program do maszyny Turinga

Witam.

Bardzo fajna strona. Przydatna podczas nauki teorii informatyki. Udało mi się napisać program dla maszyny Turinga, który sortuje bity w liczbie binarnej (zera daje na lewo, a jedynki na prawo). Może komuś się jeszcze przyda. Poniżej zamieszczam kod źródłowy.

Program
// stan q0 - początkowy ?,q0,?,q0,R 0,q0,0,q0,R 1,q0,0,q1,R // stan q1 - wykryto 1 podążając z lewej strony ?,q1,?,q2,L 0,q1,0,q1,R 1,q1,1,q1,R // stan q2 - osiągnięto koniec liczby podążając z lewej strony ?,q2,?,q6,R 0,q2,1,q3,L 1,q2,1,q2,L // stan q3 - wykryto 0 podążając z prawej strony ?,q3,?,q6,L 0,q3,0,q4,L 1,q3,1,q4,L // stan q4 - wystąpiło 0 po sekwencji jedynek ?,q4,?,q6,L 0,q4,0,q4,L 1,q4,1,q5,L // stan q5 - sekwencja znaków jest nieposortowana ?,q5,?,q0,R 0,q5,0,q5,L 1,q5,1,q5,L // stan q6 - stan końcowy, maszyna kończy działanie

Program

// stan q0 - początkowy
?,q0,?,q0,R
0,q0,0,q0,R
1,q0,0,q1,R
// stan q1 - wykryto 1 podążając z lewej strony
?,q1,?,q2,L
0,q1,0,q1,R
1,q1,1,q1,R
// stan q2 - osiągnięto koniec liczby podążając z lewej strony
?,q2,?,q6,R
0,q2,1,q3,L
1,q2,1,q2,L
// stan q3 - wykryto 0 podążając z prawej strony
?,q3,?,q6,L
0,q3,0,q4,L
1,q3,1,q4,L
// stan q4 - wystąpiło 0 po sekwencji jedynek
?,q4,?,q6,L
0,q4,0,q4,L
1,q4,1,q5,L
// stan q5 - sekwencja znaków jest nieposortowana
?,q5,?,q0,R
0,q5,0,q5,L
1,q5,1,q5,L
// stan q6 - stan końcowy, maszyna kończy działanie

Stworzyłem też kolejny program, który także sortuje liczbę binarną, ale w sposób odwrotny, niż ten, który wysłałem wcześniej, tzn. jedynki daje na lewo, a zera na prawo.

Program
// sortowanie odwrotne bitów liczby binarnej // głowica powinna zacząć działanie z lewej strony // stan q0 - początkowy ?,q0,?,q0,R 0,q0,1,q1,R 1,q0,1,q0,R // stan q1 - wystąpiło 0 podążając z lewej strony ?,q1,?,q2,L 0,q1,0,q1,R 1,q1,1,q1,R // stan q2 - osiągnięto koniec liczby podążając z lewej strony ?,q2,?,q6,L 0,q2,0,q2,L 1,q2,0,q3,L // stan q3 - wystąpiła 1 podążając z prawej strony ?,q3,?,q6,L 0,q3,0,q3,L 1,q3,1,q4,L // stan q4 - wystąpiła 1 po sekwencji zer ?,q4,?,q6,L 0,q4,0,q5,L 1,q4,1,q4,L // stan q5 - liczba jest nieposortowana ?,q5,?,q0,R 0,q5,0,q5,L 1,q5,1,q5,L // stan q6 - stan końcowy, maszyna kończy działanie

Program

// sortowanie odwrotne bitów liczby binarnej
// głowica powinna zacząć działanie z lewej strony
// stan q0 - początkowy
?,q0,?,q0,R
0,q0,1,q1,R
1,q0,1,q0,R
// stan q1 - wystąpiło 0 podążając z lewej strony
?,q1,?,q2,L
0,q1,0,q1,R
1,q1,1,q1,R
// stan q2 - osiągnięto koniec liczby podążając z lewej strony
?,q2,?,q6,L
0,q2,0,q2,L
1,q2,0,q3,L
// stan q3 - wystąpiła 1 podążając z prawej strony
?,q3,?,q6,L
0,q3,0,q3,L
1,q3,1,q4,L
// stan q4 - wystąpiła 1 po sekwencji zer
?,q4,?,q6,L
0,q4,0,q5,L
1,q4,1,q4,L
// stan q5 - liczba jest nieposortowana
?,q5,?,q0,R
0,q5,0,q5,L
1,q5,1,q5,L
// stan q6 - stan końcowy, maszyna kończy działanie

Podczas przygotowywania się do kolokwium z teorii informatyki stworzyłem kolejny program. Tym razem porównuje on 2 ciągi i sprawdza, który jest większy lub czy są one sobie równe.

Program
// sprawdzanie, który z 2 ciągów rozdzielonych // kropką jest większy. Ciągi muszą się składać // ze znaków A. Przykładowy format ciągów: ?AA.AAA? // głowica powinna być umieszczona na kropce // stan q0 ?,q0,?,q2,L A,q0,.,q1,L .,q0,.,q0,R // stan q1 ?,q1,?,q3,R A,q1,.,q0,R .,q1,.,q1,L // stan q2 ?,q2,?,równe,L A,q2,A,lewy,L .,q2,.,q2,L // stan q3 ?,q3,?,równe,R A,q3,A,prawy,R .,q3,.,q3,R // stan: równe - ciągi są równe // stan: prawy - prawy ciąg jest większy // stan: lewy - lewy ciąg jest większy

Program

// sprawdzanie, który z 2 ciągów rozdzielonych
// kropką jest większy. Ciągi muszą się składać
// ze znaków A. Przykładowy format ciągów: ?AA.AAA?
// głowica powinna być umieszczona na kropce

// stan q0
?,q0,?,q2,L
A,q0,.,q1,L
.,q0,.,q0,R
// stan q1
?,q1,?,q3,R
A,q1,.,q0,R
.,q1,.,q1,L
// stan q2
?,q2,?,równe,L
A,q2,A,lewy,L
.,q2,.,q2,L
// stan q3
?,q3,?,równe,R
A,q3,A,prawy,R
.,q3,.,q3,R

// stan: równe - ciągi są równe
// stan: prawy - prawy ciąg jest większy
// stan: lewy  - lewy ciąg jest większy

Witam. Sesja w pełni, więc przesyłam kolejny program ;-)

Program
// program zamienia pierwsze 3 litery w pojedynczym // ciągu na duże, a resztę na małe. Ciągi znaków // składają się z liter: a,b,c,A,B,C // Ciągi są rozdzielone znakiem _ // przykładowy format ciągów: ?aAbcAbbACCBbA_AbbC_CaBaacBCaBa? // głowica powinna rozpocząć działanie z lewej strony // stan q0 - szukamy początku ciągu, // jak znajdziemy, to zamieniamy pierwszą literę ?,q0,?,q0,R a,q0,A,q1,R b,q0,B,q1,R c,q0,C,q1,R A,q0,A,q1,R B,q0,B,q1,R C,q0,C,q1,R _,q0,_,q0,R // stan q1 - pierwsza litera została zmieniona, // zamieniamy drugą ?,q1,?,q0,R a,q1,A,q2,R b,q1,B,q2,R c,q1,C,q2,R A,q1,A,q2,R B,q1,B,q2,R C,q1,C,q2,R _,q1,_,q0,R // stan q2 - druga litera została zmieniona, // zamieniamy trzecią ?,q2,?,q0,R a,q2,A,q3,R b,q2,B,q3,R c,q2,C,q3,R A,q2,A,q3,R B,q2,B,q3,R C,q2,C,q3,R _,q2,_,q0,R // stan q3 - trzecia litera została zmieniona, // zamieniamy resztę na małe i szukamy końca // jednego ciągu lub końca wszystkich ciągów ?,q3,?,q4,R a,q3,a,q3,R b,q3,b,q3,R c,q3,c,q3,R A,q3,a,q3,R B,q3,b,q3,R C,q3,c,q3,R _,q3,_,q0,R // stan q4 - koniec ciągów - koniec programu

Program

// program zamienia pierwsze 3 litery w pojedynczym
// ciągu na duże, a resztę na małe. Ciągi znaków
// składają się z liter: a,b,c,A,B,C
// Ciągi są rozdzielone znakiem _
// przykładowy format ciągów: ?aAbcAbbACCBbA_AbbC_CaBaacBCaBa?
// głowica powinna rozpocząć działanie z lewej strony

// stan q0 - szukamy początku ciągu,
// jak znajdziemy, to zamieniamy pierwszą literę
?,q0,?,q0,R
a,q0,A,q1,R
b,q0,B,q1,R
c,q0,C,q1,R
A,q0,A,q1,R
B,q0,B,q1,R
C,q0,C,q1,R
_,q0,_,q0,R
// stan q1 - pierwsza litera została zmieniona,
// zamieniamy drugą
?,q1,?,q0,R
a,q1,A,q2,R
b,q1,B,q2,R
c,q1,C,q2,R
A,q1,A,q2,R
B,q1,B,q2,R
C,q1,C,q2,R
_,q1,_,q0,R
// stan q2 - druga litera została zmieniona,
// zamieniamy trzecią
?,q2,?,q0,R
a,q2,A,q3,R
b,q2,B,q3,R
c,q2,C,q3,R
A,q2,A,q3,R
B,q2,B,q3,R
C,q2,C,q3,R
_,q2,_,q0,R
// stan q3 - trzecia litera została zmieniona,
// zamieniamy resztę na małe i szukamy końca
// jednego ciągu lub końca wszystkich ciągów
?,q3,?,q4,R
a,q3,a,q3,R
b,q3,b,q3,R
c,q3,c,q3,R
A,q3,a,q3,R
B,q3,b,q3,R
C,q3,c,q3,R
_,q3,_,q0,R
// stan q4 - koniec ciągów - koniec programu

Czas:  2015-06-10 13:22:28
URL:   /inf/prg/003_mt/0003.php
Tytuł: Maszyna Turinga - Symulator maszyny Turinga
Temat: Własne programy maszyny Turinga

Program zamienia cyfry 0-1 na 1. Na taśmie należy umieścić dowolny ciąg cyfr 0 i 1, np.: ?01011000101. Następnie głowicę maszyny ustawiamy na ostatniej cyfrze i uruchamiamy poniższy kod

Program
0,q0,1,q0,L 1,q0,1,q1,L 0,q1,1,q1,L 1,q1,1,q2,L 1,q2,1,q2,L 0,q2,1,q3,L ?,q3,1,q0,L

Kolejny program zamienia litery A, B i C na D. Na taśmie umieszczamy dowolny ciąg liter A, B i C, np.: ?AACBABCBB. Głowicę ustawiamy na ostatniej literze i uruchamiamy kod:

Program
C,q0,D,q0,L B,q0,D,q0,L A,q0,D,q0,L

Dzień dobry, przesyłam instrukcje maszyny Turinga do dodania liczby binarnej 101 do jakiejkolwiek innej liczby binarnej.

Q = {q0,q1,q2,q3,q4,q5,q6,q7}
∑ = {0, 1}
Γ = {0, 1, X, θ}
A = {q7}
q0 = {q0}
δ = Q ´ Γ → Q ´ Γ ´{L, R}

gdzie

A - zbiór stanów końcowych, akceptujących,
A ⊆ Q.Q - skończony zbiór stanów,
q0 - stan początkowy, q0 ∈ Q,
Σ - skończony zbiór alfabetu, zbiór symboli wejściowych,
Γ - alfabet taśmy, skończony zbiór właściwych symboli na taśmie, przy czym Σ ⊂ Γ − {Θ} (alfabet wejściowy jest podzbiorem alfabetu taśmy, z wyjątkiem symbolu pustego),
Θ - symbol pusty, Θ ∈ Γ, traktowany jako zakończenie sekwencji wejściowej,
δ(q, a) - funkcja przejścia: δ : Q × Γ → Q × Γ × {L, R},
funkcja δ przypisuje stan docelowy, symbol zapisywany na taśmie oraz kierunek ruchu głowicy (L - lewo, R - prawo),
q0 - stan początkowy, q0 ∈ Q,

Program
1,q0,1,q0,R 0,q0,0,q0,R x,q0,x,q1,L 1,q1,0,q2,L 0,q1,1,q3,L x,q1,1,q3,L 1,q2,0,q4,L 0,q2,1,q5,L x,q2,1,q5,L 1,q3,1,q5,L 0,q3,0,q5,L x,q3,0,q5,L 1,q3,1,q5,L 0,q3,0,q5,L x,q3,0,q5,L 1,q4,1,q6,L 0,q4,0,q6,L x,q4,0,q6,L 1,q5,0,q6,L 0,q5,1,q7,L x,q5,1,q7,L 1,q6,0,q6,L 0,q6,1,q7,L x,q6,1,q7,L

Program

1,q0,1,q0,R
0,q0,0,q0,R
x,q0,x,q1,L
1,q1,0,q2,L
0,q1,1,q3,L
x,q1,1,q3,L
1,q2,0,q4,L
0,q2,1,q5,L
x,q2,1,q5,L
1,q3,1,q5,L
0,q3,0,q5,L
x,q3,0,q5,L
1,q3,1,q5,L
0,q3,0,q5,L
x,q3,0,q5,L
1,q4,1,q6,L
0,q4,0,q6,L
x,q4,0,q6,L
1,q5,0,q6,L
0,q5,1,q7,L
x,q5,1,q7,L
1,q6,0,q6,L
0,q6,1,q7,L
x,q6,1,q7,L

Pozdrawiam, Sandra Zmysłowska

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.