Ngôn ngữ được chấp nhận & Ngôn ngữ quyết định

Một TM chấp nhận một ngôn ngữ nếu nó đi vào trạng thái cuối cùng cho bất kỳ chuỗi đầu vào w. Một ngôn ngữ có thể liệt kê một cách đệ quy (được tạo bởi ngữ pháp Kiểu-0) nếu nó được máy Turing chấp nhận.

Một TM quyết định một ngôn ngữ nếu nó chấp nhận nó và chuyển sang trạng thái từ chối cho bất kỳ đầu vào nào không phải bằng ngôn ngữ đó. Một ngôn ngữ là đệ quy nếu nó được quyết định bởi máy Turing.

Có thể có một số trường hợp TM không dừng lại. TM như vậy chấp nhận ngôn ngữ, nhưng nó không quyết định nó.

Thiết kế máy Turing

Các hướng dẫn cơ bản về thiết kế máy Turing đã được giải thích dưới đây với sự trợ giúp của một số ví dụ.

ví dụ 1

Thiết kế một TM để nhận ra tất cả các chuỗi bao gồm một số lẻ của α.

Solution

Máy Turing M có thể được xây dựng bằng các bước sau:

Để cho q₁ là trạng thái ban đầu.
Nếu M trong q₁; khi quét α, nó chuyển sang trạng tháiq₂ và viết B (chỗ trống).
Nếu M trong q₂; khi quét α, nó chuyển sang trạng tháiq₁ và viết B (chỗ trống).
Từ những động thái trên, chúng ta có thể thấy rằng M vào tiểu bang q₁ nếu nó quét một số chẵn của α và nó đi vào trạng thái q₂nếu nó quét một số lẻ của α. Vì thếq₂ là trạng thái chấp nhận duy nhất.

Vì thế,

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

trong đó δ được đưa ra bởi -

Biểu tượng bảng chữ cái băng	Trạng thái hiện tại 'q ₁ '	Trạng thái hiện tại 'q ₂ '
α	BRq ₂	BRq ₁

Ví dụ 2

Thiết kế một Máy Turing đọc một chuỗi biểu thị một số nhị phân và xóa tất cả các số 0 đứng đầu trong chuỗi. Tuy nhiên, nếu chuỗi chỉ bao gồm các số 0, nó sẽ giữ một số 0.

Solution

Giả sử rằng chuỗi đầu vào được kết thúc bằng một ký hiệu trống, B, ở mỗi đầu của chuỗi.

Máy Turing, M, có thể được xây dựng bằng các bước sau:

Để cho q₀ là trạng thái ban đầu.
Nếu M trong q₀, khi đọc 0, nó di chuyển sang phải, đi vào trạng thái q₁ và xóa 0. Khi đọc 1, nó chuyển sang trạng thái q₂ và di chuyển sang phải.
Nếu M trong q₁, khi đọc số 0, nó di chuyển sang phải và xóa số 0, tức là nó thay thế số 0 bằng số B. Khi đến ngoài cùng bên trái 1, nó đi vàoq₂và di chuyển sang phải. Nếu nó đến B, tức là, chuỗi chỉ bao gồm các số 0, nó sẽ di chuyển sang trái và chuyển sang trạng tháiq₃.
Nếu M trong q₂, khi đọc 0 hoặc 1, nó di chuyển sang phải. Khi đến B, nó di chuyển sang trái và đi vào trạng tháiq₄. Điều này xác nhận rằng chuỗi chỉ bao gồm 0 và 1.
Nếu M trong q₃, nó thay thế B bằng 0, di chuyển sang trái và đạt đến trạng thái cuối cùng q_f.
Nếu M trong q₄, khi đọc 0 hoặc 1, nó sẽ di chuyển sang trái. Khi đến đầu chuỗi, tức là khi nó đọc B, nó đạt đến trạng thái cuối cùngq_f.