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

Xây máy Turing cho L = {a^i b^j c^k | i*j=k; i,j,k≥1}

Xây máy Turing cho L = {aibjck | i × j = k; i,j,k ≥ 1}. Ví dụ: AABBBBCCCCCCCC (2×4=8) được chấp nhận.

Phương pháp

  1. Thay A→X, đi phải qua các A
  2. Gặp B đầu → B→Y, đi phải qua B, C đầu → C→Z, đi trái
  3. Đi trái qua Z,B đến Y gần nhất → đi phải
  4. Nếu trỏ B: lặp bước 2-4. Nếu trỏ Z: đi trái, Y→B, qua A
  5. Gặp X gần nhất → đi phải
  6. Nếu vẫn là A: lặp tất cả. Nếu là Y: đi phải qua Y,Z đến $
  7. Gặp $ → đi trái, chấp nhận

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

Xây máy Turing cho L = {a^i b^j c^k | i*j=k; i,j,k≥1}