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ć q1 być stanem początkowym.

  • Jeśli M jest w q1; przy skanowaniu α wchodzi w stanq2 i pisze B (pusty).

  • Jeśli M jest w q2; przy skanowaniu α wchodzi w stanq1 i pisze B (pusty).

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

W związku z tym,

M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}

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ć q0 być stanem początkowym.

  • Jeśli M jest w q0po odczytaniu 0 przesuwa się w prawo, wchodzi w stan q1 i usuwa 0. Przy odczycie 1 wchodzi w stan q2 i porusza się w prawo.

  • Jeśli M jest w q1, po przeczytaniu 0, przesuwa się w prawo i kasuje 0, tj. zastępuje 0 przez B. Po osiągnięciu skrajnej lewej cyfry 1, wchodziq2i 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 stanq3.

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

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

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

W związku z tym,

M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , 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