BÀI TẬP CHƯƠNG VII

Thiết kế máy Turing nhận diện ngôn ngữ:

a) { 0ⁿ 1ⁿ 0ⁿ | n ³ 1}

b) {ww ^R | w Î (0+1)^*}

c) Tập hợp các chuỗi chứa 0 và 1, có số số 0 và số số 1 bằng nhau.

Thiết kế máy Turing tính các hàm số nguyên:

a) f(n) = n²

b) f(n) = 2ⁿ

c) f(n) = n !

Xây dựng văn phạm không hạn chế (loại 0) sinh ra các ngôn ngữ sau:

a) { ww^{| w Î (0+1)*}}

b) { 0^k | k = i² và i ³ 1}

c) { 0ⁱ | i không là số nguyên tố}

BÀI TẬP LẬP TRÌNH

Viết chương trình máy tính mô phỏng hoạt động của các TM thiết kế trong bài tập 7.1 và 7.2.