Wydział Techniki	Uniwersytet Śląski	Data
				21-01-1999
	Zakład Systemów Informatycznych
			Zadania z maszyny Turing'a.
Sprawozdanie numer 3.	Paweł Kopaczek	Ocena ................
	Piotr Kopaczek	Podpis ...............

Zestaw 4.

Szczegółowe polecenia do wszystkich zadań:

• podaj słowny algorytm rozwiązania

• zdefiniuj Q, Γ, δ, q₀, B, F

• wykonaj tabelę stanów (lub graf przejść)

• sprawdź rozwiązanie na wybranym przykładzie

Zad.1.

Dla alfabetu: Σ = { a, b, c } skonstruować tablicę przejść maszyny Turinga, która dokonuje transformacji słowa u na v, gdzie v otrzymujemy z u poprzez usunięcie co drugiego symbolu ( poczynając od drugiego ).

Przykłady:

WE: baccacbb WY: acab

Zad.2.

Skonstruować tablicę przejść maszyny Turinga, która dokonuje transformacji liczby zapisanej w kodzie ZU2 na zapis Znak-Moduł.

Zad.3.

Skonstruować tablice przejść maszyny Turinga, która dokonuje przesunięcia ułamka binarnego zapisanego w kodzie ZU2 w lewo o zadaną liczbę pozycji.

Przykłady:

WE: 0.1101 ← 2 WY: 0.0100

WE: 1.00010 ← 1 WY: 1.00100

Zadanie.1.

Q Σ

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q13

q14

∅

q14 - -

q2 ∅ P

q3 a L

q4 ∅L

q13 a P

q6 ∅ P

q7 b L

q8 ∅L

q13 b P

q1 ∅ P

q11 c L

q1 ∅L

q13 c P

q14 - -

q14 - -

A

q1 ∅ P

q1 a P

q2 a P

q3 a L

q4 a L

q5 a P

q6 a P

q7 a L

q8 a L

q9 a P

q10 a P

Q11 a L

q12 a L

q0 a P

q14 - -

B

q5 ∅ P

q1 b P

q2 b P

q3 b L

q4 b L

q5 b P

q6 b P

q7 b L

q8 b L

q9 b P

q10 b P

Q11 b L

q12 b L

q0 a P

q14 - -

C

q9 ∅ P

q1 c P

q2 c P

q3 c L

q4 c L

q5 c P

q6 c P

q7 c L

q8 c L

q9 c P

q10 c P

Q11 c L

q12 c L

q0 c P

q14 - -

M_t = < Q, ∑, F, , q_o, δ>

Q = { q₀ - q₁₄ },

∑ = { a,b,c},

 = { ∅ } ∪ ∑,

q_o - stan początkowy,

F = { q₁₄ },

δ : Q x F →Q x F x { L, P, -}

Kopiujemy --> dan[Author:PK] ą

Przykład.

b a c b a c

Zaczynamy od 1 literki b, przesuwamy się nad literkę a. Kasujemy literkę a i przechodzimy w prawo omijając słowo pierwsze, separator aż do napotkania znaku ∅. Wpisujemy literkę a i wracamy omijając drugie słowo, separator i słowo pierwsze aż do napotkania znaku ∅ gdzie odtwarzamy literkę a, przesuwamy się w prawo omijając literkę c.

Kasujemy literkę b i przechodzimy w prawo omijając słowo pierwsze, separator, słowo drugie aż do napotkania znaku ∅. Wpisujemy literkę b i wracamy omijając drugie słowo, separator i słowo pierwsze aż do napotkania znaku ∅ gdzie odtwarzamy literkę a, przesuwamy się w prawo omijając literkę a.

Kasujemy literkę c i przechodzimy w prawo omijając separator, drugie słowo aż do napotkania znaku ∅. Wpisujemy literkę a i wracamy omijając drugie słowo, separator i słowo pierwsze aż do napotkania znaku ∅ gdzie odtwarzamy literkę c omijając literkę c.

Zadanie 2.

Q ∑	q0	q1	q2	q3	q4
∅	q0 - -	q2 L ∅	q2 - -	q3 - -	q4 _- -
0	q4 - -	q1 P 0	q2 L 0	q3 L 1	q4 - -
1	q1 P 1	q1 P 1	q3 L 1	q3 L 0	q4 - -
•	q0 - -	q4 P •	q4 - -	q4 - -	q4 - -

M_t = < Q, ∑, F, , q_o, δ>

Q = { q_o - q₄ },

∑ = { 0, 1},

 = { ∅ } ∪ ∑,

q_o - stan początkowy,

F = { q₄ },

δ : Q x F →Q x F x { L, P, -}

Znajdujemy się nad bitem znakowym, jeśli jest 0 to robimy skok do stanu q_4. Jeśli nie przesuwamy się na sam koniec wyrazu ( w q₁ aż do napotkania znaku pustego i cofnięcie w lewo). Skok do q_2. Jeśli wystąpi 0 lub 1 to przechodzimy w prawo, aż napotkamy 1. Po wykryciu 1 przechodzimy do q₃ gdzie negujemy wartości bitów. Po napotkaniu kropki kończymy program.

Przykład:

a)1.011010

Odczytujemy 1 na bicie znakowym i idziemy w prawo aż dojdziemy na sam koniec słowa.

0 - pozostawiamy 0 i przesuwamy się w lewo.

1 - pozostawiamy 1 i przesuwamy się w lewo.

0 - zmieniamy na 1 i przesuwamy się w lewo.

1 - zmieniamy na 0 i przesuwamy się w lewo.

1 - zmieniamy na 0 i przesuwamy się w lewo.

0 - zmieniamy na 1 i przesuwamy się w lewo.

Napotykamy kropkę kończącą wykonywanie zadania.

a)0.101101

Odczytujemy 0 na bicie znakowym, kończymy pracę.

Zadanie 3.

Q ∑	q0	q1	q2	q3	q4
∅	q4 - -	q4 - -	q4 - -	q4 - -	q4 - -
0	q0 P 0	q4 P 0	q2 L 0	q2 L 1	q4 - -
1	q0 P 1	q2 L 0	q3 L 0	q3 L 1	q4 - -
2	q0 - -	q2 L 1	q1 - -	q1 - -	q4 - -
←	q1 P ←	q1 - -	q2 L ←	q1 - -	q4 - -
•	q0 P .	q1 - -	q2 - -	q0 P .	q4 - -

M_t = < Q, ∑, F, , q_o, δ>

Q = { q_o - q₄ },

∑ = { 0, 1, 2, ←, . },

 = { ∅ } ∪ ∑,

q_o - stan początkowy,

F = { q₄ },

δ : Q x F →Q x F x { L, P, -}

1. W q_o przechodzimy za całe słowo i znak „←” nad cyfrę określającą przesunięcie.

2. Sprawdzamy wartość bieżącej cyfry, jeśli równa się 0 kończymy program, jeśli nie, zmniejszam wartość o 1.

3. Przechodzimy w lewo za znak „←”. Na pierwszej napotkanej cyfrze wpisujemy wartość 0, jeśli zapisaliśmy to na 1 to na następnej cyfrze wpiszemy 1 (skok do q₃), jeśli zapisaliśmy to na 0 to na następnej cyfrze wpisze 0 ( skok do q₂).

4. Jeśli napotkamy „•” skaczemy do q₀ i powtarzamy cały algorytm od początku.

Przykład:

Przechodzimy za 1,słowo za „←”, czytamy 1, wpisujemy 0.

Przesuwamy się w lewo za „←”.

Jesteśmy nad 0, wpisujemy 0, idziemy w lewo.

Jesteśmy nad 1, wpisujemy 0, idziemy w lewo.

Jesteśmy nad 0, wpisujemy 1, idziemy w lewo.

Jesteśmy nad 0, wpisujemy 0, idziemy w lewo.

Jesteśmy nad 0, wpisujemy 0, idziemy w lewo.

Jesteśmy nad „•”, idziemy w prawo za „←”, czytamy 0, kończymy program.

2

1

---