Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Maszyna Turinga

Listy od czytelników

SPIS TREŚCI

Listy

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

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 odbijający lustrzanie liczbę binarną po jej prawej stronie.

"-" znak wypełnienia taśmy

Przykład:

przed

--1011---

po

--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 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

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

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

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

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

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

 

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.