Khả năng phân định ngôn ngữ
Một ngôn ngữ được gọi là Decidable hoặc là Recursive nếu có một máy Turing chấp nhận và tạm dừng trên mọi chuỗi đầu vào w. Mọi ngôn ngữ quyết định đều là Turing-Acceptable.
Một vấn đề quyết định P là quyết định nếu ngôn ngữ L trong số tất cả các trường hợp có cho P là quyết định.
Đối với ngôn ngữ có thể phân giải, đối với mỗi chuỗi đầu vào, TM sẽ tạm dừng ở trạng thái chấp nhận hoặc từ chối như được mô tả trong sơ đồ sau:
ví dụ 1
Tìm hiểu xem vấn đề sau có phải là giải hay không:
Một số 'm' có phải là số nguyên tố không?
Giải pháp
Số nguyên tố = {2, 3, 5, 7, 11, 13, ………… ..}
Chia số ‘m’ bởi tất cả các số từ '2' đến '√m' bắt đầu từ '2'.
Nếu bất kỳ số nào trong số này tạo ra phần dư là 0, thì nó chuyển sang “Trạng thái bị từ chối”, nếu không nó sẽ chuyển sang “Trạng thái được chấp nhận”. Vì vậy, ở đây câu trả lời có thể là 'Có' hoặc 'Không'.
Hence, it is a decidable problem.
Ví dụ 2
Cho một ngôn ngữ thông thường L và chuỗi w, làm thế nào chúng tôi có thể kiểm tra nếu w ∈ L?
Giải pháp
Lấy DFA chấp nhận L và kiểm tra xem w được chấp nhận
Một số vấn đề khó giải quyết hơn là -
- DFA có chấp nhận ngôn ngữ trống không?
- L 1 ∩ L 2 = ∅ có phải là tập hợp chính quy không?
Note -
Nếu một ngôn ngữ L là quyết định, sau đó bổ sung của nó L' cũng có thể quyết định
Nếu một ngôn ngữ có thể phân biệt được thì sẽ có một điều tra viên cho nó.