Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Xây máy Turing cho ngôn ngữ L = {0^n 1^n 2^n | n≥1}

Xây máy Turing cho L = {0n1n2n | n ≥ 1}. Chuỗi n số 0, n số 1, n số 2. Ví dụ: 000111222 được chấp nhận.

Phương pháp

  1. Thay 0 đầu bằng X, đi phải tìm 1 đầu → thay Y
  2. Đi phải tìm 2 đầu → thay Z, đi trái
  3. Đi trái tìm X, khi thấy X → đi phải 1 bước
  4. Lặp lại quy trình trên
  5. Điều kiện dừng: gặp X ngay sau đó là Y → kiểm tra tất cả 1,2 đã thành Y,Z chưa. Nếu còn 1/2 → từ chối. Nếu gặp $ (cuối băng) → chấp nhận

Sơ đồ chuyển trạng thái

Xây máy Turing cho ngôn ngữ L = {0^n 1^n 2^n | n≥1}