Tìm cặp biểu thức chính quy tương đương nhau

Đáp án đúng: D

Để xác định cặp biểu thức chính quy tương đương, ta cần hiểu rõ ý nghĩa của các ký hiệu:

A. (0+1)* và (0*+1*)*

(0+1)*: Chuỗi gồm 0 hoặc 1, lặp lại không hoặc nhiều lần. Ví dụ: "", "0", "1", "00", "01", "10", "11", "000",...
(0*+1*)*: Chuỗi gồm các chuỗi 0 lặp lại không hoặc nhiều lần HOẶC chuỗi 1 lặp lại không hoặc nhiều lần, tất cả lặp lại không hoặc nhiều lần. Ví dụ: "", "0", "1", "00", "11", "000", "111", "0011", "1100",... Cả hai biểu thức này đều mô tả tập hợp tất cả các chuỗi nhị phân (chuỗi chỉ chứa 0 và 1). Vì vậy, chúng tương đương.

B. (0+1)* và (0+1*)*

(0+1)*: Như trên, tập hợp tất cả các chuỗi nhị phân.
(0+1*)*: Chuỗi gồm 0 HOẶC chuỗi 1 lặp lại không hoặc nhiều lần, tất cả lặp lại không hoặc nhiều lần. Biểu thức này KHÔNG tương đương với (0+1)* vì nó không thể tạo ra chuỗi "10". Ví dụ, chuỗi "10" không thể được tạo ra từ biểu thức này, vì sau khi chọn "1*", nó sẽ chỉ sinh ra các chuỗi "1", "11", "111",... và không thể xen kẽ "0" vào giữa.

C. (0+10)* và (0*+10)*

(0+10)*: Chuỗi gồm 0 HOẶC 10, lặp lại không hoặc nhiều lần. Ví dụ: "", "0", "10", "00", "010", "100", "1010",... Biểu thức này không thể tạo ra chuỗi "1".
(0*+10)*: Chuỗi gồm các chuỗi 0 lặp lại không hoặc nhiều lần HOẶC 10, tất cả lặp lại không hoặc nhiều lần. Ví dụ: "", "0", "10", "00", "010", "100", "1010", "0010",... Biểu thức này cũng không thể tạo ra chuỗi "1". Tuy nhiên, xét chuỗi "010". (0+10)* có thể tạo ra chuỗi này. (0*+10)* cũng có thể tạo ra chuỗi này. Nhưng chuỗi "1" thì không thể tạo ra từ cả hai. Vậy hai biểu thức này không tương đương.

D. Tất cả các cặp đều tương đương: Sai vì B và C không tương đương.

Vậy đáp án đúng là A.