Zaakceptowany język i zdecydowany język

Baza TM akceptuje język, jeśli wejdzie w stan końcowy dla dowolnego ciągu wejściowego w. Język jest rekurencyjnie wyliczalny (generowany przez gramatykę typu 0), jeśli jest akceptowany przez maszynę Turinga.

TM decyduje o języku, jeśli go akceptuje, i przechodzi w stan odrzucenia dla wszelkich danych wejściowych spoza tego języka. Język jest rekurencyjny, jeśli decyduje o nim maszyna Turinga.

Mogą wystąpić przypadki, w których baza TM się nie zatrzymuje. Taka TM akceptuje język, ale o tym nie decyduje.

Projektowanie maszyny Turinga

Podstawowe wskazówki dotyczące projektowania maszyny Turinga zostały wyjaśnione poniżej na kilku przykładach.

Przykład 1

Zaprojektuj TM tak, aby rozpoznawała wszystkie ciągi składające się z nieparzystej liczby α.

Solution

Maszyna Turinga M można zbudować za pomocą następujących ruchów -

• Pozwolić q₁ być stanem początkowym.

• Jeśli M jest w q₁; przy skanowaniu α wchodzi w stanq₂ i pisze B (pusty).

• Jeśli M jest w q₂; przy skanowaniu α wchodzi w stanq₁ i pisze B (pusty).

• Z powyższych ruchów możemy to zobaczyć M wchodzi do stanu q₁ jeśli skanuje parzystą liczbę α i wchodzi w stan q₂jeśli skanuje nieparzystą liczbę α. W związku z tymq₂ jest jedynym stanem akceptującym.

W związku z tym,

M = {{q ₁ , q ₂ }, {1}, {1, B}, δ, q ₁ , B, {q ₂ }}

gdzie δ jest podane przez -

Symbol alfabetu taśmy	Stan obecny „q 1 ”	Stan obecny „q 2 ”
α	BRq 2	BRq 1

Przykład 2

Zaprojektuj maszynę Turinga, która czyta łańcuch reprezentujący liczbę binarną i usuwa wszystkie wiodące zera w ciągu. Jeśli jednak ciąg składa się tylko z zer, zachowuje jedno 0.

Solution

Załóżmy, że ciąg wejściowy jest zakończony pustym symbolem B na każdym końcu łańcucha.

Maszyna Turinga, M, można zbudować za pomocą następujących ruchów -

• Pozwolić q₀ być stanem początkowym.

• Jeśli M jest w q₀po odczytaniu 0 przesuwa się w prawo, wchodzi w stan q₁ i usuwa 0. Przy odczycie 1 wchodzi w stan q₂ i porusza się w prawo.

• Jeśli M jest w q₁, po przeczytaniu 0, przesuwa się w prawo i kasuje 0, tj. zastępuje 0 przez B. Po osiągnięciu skrajnej lewej cyfry 1, wchodziq₂i porusza się w prawo. Jeśli osiągnie B, czyli ciąg składa się tylko z zer, przesuwa się w lewo i wchodzi w stanq₃.

• Jeśli M jest w q₂, po odczytaniu 0 lub 1 przesuwa się w prawo. Po osiągnięciu B przesuwa się w lewo i wchodzi w stanq₄. To potwierdza, że ​​ciąg składa się tylko z zer i jedynek.

• Jeśli M jest w q₃, zastępuje B przez 0, przesuwa się w lewo i osiąga stan końcowy q_f.

• Jeśli M jest w q₄po odczytaniu 0 lub 1 przesuwa się w lewo. Po osiągnięciu początku łańcucha, tj. Gdy odczytuje B, osiąga stan końcowyq_f.

W związku z tym,

M = {{q ₀ , q ₁ , q ₂ , q ₃ , q ₄ , q _f }, {0,1, B}, {1, B}, δ, q ₀ , B, {q _f }}

gdzie δ jest podane przez -

Symbol alfabetu taśmy	Stan obecny „q 0 ”	Stan obecny „q 1 ”	Stan obecny „q 2 ”	Stan obecny „q 3 ”	Stan obecny „q 4 ”
0	BRq 1	BRq 1	ORq 2	-	OLq 4
1	1Rq 2	1Rq 2	1Rq 2	-	1Lq 4
b	BRq 1	BLq 3	BLq 4	OLq f	BRq f