bài tập chương II ngôn ngữ và biểu diễn ngôn ngữ

Chứng minh hoặc bác bỏ : L⁺ = L^* - {ε}.

L⁺ hay L^* có thể bằng ∅ không ? Khi nào thì L⁺ hay L^* là hữu hạn ?

Hãy cho biết các thứ tự cho phép liệt kê các phần tử của các ngôn ngữ sau :

a) {a, b}^*

b) {a}^*{b}^*{c}^*

c) {w | w ∈{a, b}⁺ và số a bằng số b trong w}

Một chuỗi hình tháp có thể định nghĩa là một chuỗi đọc xuôi hay ngược đều như nhau, hoặc cũng có thể định nghĩa như sau :

1) ε là chuỗi hình tháp.

2) Nếu a là một ký hiệu bất kỳ thì a là một chuỗi hình tháp.

3) Nếu a là một ký hiệu bất kỳ và X là một chuỗi hình tháp thì aXa là một chuỗi hình tháp.

4) Không còn chuỗi hình tháp nào ngoài các chuỗi cho từ (1) đến (3).

Hãy chứng minh quy nạp rằng 2 định nghĩa trên là tương đương.

Các chuỗi ngoặc đơn cân bằng được định nghĩa theo 2 cách :

Cách 1 : Một chuỗi w trên bộ chữ cái { ( , ) } là cân bằng khi và chỉ khi :

a) w chứa cùng một số ')' và '('

b) Mọi tiền tố của w chứa số các '(' ít nhất bằng số các ')'.

Cách 2 :

a) ( là chuỗi ngoặc đơn cân bằng

b) Nếu w là một chuỗi ngoặc đơn cân bằng, thì (w) là chuỗi ngoặc đơn cân bằng.

c) Nếu w và x là các chuỗi ngoặc đơn cân bằng, thì wx là chuỗi ngoặc đơn cân bằng.

d) Không còn chuỗi ngoặc đơn cân bằng nào khác với trên.

Hãy chứng minh bằng quy nạp theo độ dài chuỗi rằng 2 định nghĩa trên là tương đương.