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

Xây máy Turing cho L = {aⁱb^jc^k | i > j > k; k ≥ 1}. Chuỗi a, b, c với số lượng giảm dần. Ví dụ: aaaaaabbbbccc được chấp nhận.

Phương pháp

So sánh 2 phần tử làm 1 đơn vị (A và D). Sau đó so sánh A và D: nếu |C| > |(A,D)| → từ chối; nếu |D| > |A| → từ chối; ngược lại → chấp nhận.

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