BÀI TẬP CHƯƠNG VIII

Xây dựng văn phạm cảm ngữ cảnh 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ố}

d) { aⁱ b²ⁱ c³ⁱ | i ³ 1}

e) { aⁱ bⁱ c^k | i ³ 1, k ≤ 1}

Thiết kế ôtômát tuyến tính giới nội LBA đoán nhận các ngôn ngữ sau:

1. { aⁿ bⁿ cⁿ | n ³ 1}

b) { ww^{| w Î (a + b + c)*}}