Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
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 q99Poprawny 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 |
Program |
---|
C,q0,D,q0,L B,q0,D,q0,L A,q0,D,q0,L |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.