BÀI TẬP CHƯƠNG IV

Xây dựng văn phạm tuyến tính trái và tuyến tính phải cho các ngôn ngữ sau :

(0 + 1)^*00(0 + 1)^*

0^*(1(0 + 1))^*

(((01 + 10)^*11)^*00)^*

Xây dựng văn phạm chính quy sinh ra các ngôn ngữ trên bộ chữ cái Σ = {0,1} như sau :

Tập các chuỗi có chứa 3 con số 0 liên tiếp.

Tập các chuỗi kết thúc bằng 2 con số 0.

Xây dựng văn phạm chính quy sinh ra các ngôn ngữ sau :

{ w | w ∈ (0 + 1)^* }

{ a^m bⁿ | m, n > 0 }

Chứng tỏ rằng ngôn ngữ L = {0ⁿ1ⁿ | n là số nguyên dương} không chính qui.

Ngôn ngữ nào trong các ngôn ngữ sau không là ngôn ngữ chính qui? Chứng minh câu trả lời:

L = {0²ⁿ | n là số nguyên dương }

L = {0ⁿ1^m0 ^n+m | m, n là số nguyên dương}

L = {0ⁿ | n là số nguyên tố }