Biểu thức chính quy x/y ký hiệu bởi tập

Để 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:

• +: Hoặc


• *: Không hoặc nhiều lần

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.

Giải thích:

Mối quan hệ giữa ngôn ngữ được chấp nhận bởi NFA (Non-deterministic Finite Automaton) và DFA (Deterministic Finite Automaton) là bằng nhau. Điều này có nghĩa là, đối với bất kỳ ngôn ngữ nào có thể được chấp nhận bởi một NFA, luôn tồn tại một DFA chấp nhận ngôn ngữ đó, và ngược lại. Do đó, khả năng biểu diễn ngôn ngữ của hai loại máy này là tương đương nhau.

Đáp án C (=) thể hiện chính xác mối quan hệ này.