Quá trình phân tích từ vựng cho câu lệnh gán: x = y - a*2+b+c*8 sẽ tách thành bao nhiêu Từ tố số nguyên?

Văn phạm đã cho có luật sinh S -> AA. Điều này có nghĩa là mọi chuỗi sinh ra từ S đều phải là sự ghép của hai chuỗi sinh ra từ A. A có thể sinh ra "aa" hoặc "bb". Do đó, S có thể sinh ra "aaaa", "aabb", "bbaa", hoặc "bbbb".

Xét các phương án:

• Phương án A: L = {aaaa, aabb, bbaa, bbbb}. Tất cả các chuỗi đều có thể sinh ra từ văn phạm.
• Phương án B: L = {abab, abaa, aaab, baaa}. Không có chuỗi nào có thể sinh ra từ văn phạm.
• Phương án C: L = {aaab, baba, bbaa, bbbb}. Chuỗi "aaab" và "baba" không thể sinh ra từ văn phạm.
• Phương án D: L = {aaaa, abab, bbaa, aaab}. Chuỗi "abab" và "aaab" không thể sinh ra từ văn phạm.

Vậy, phương án đúng là A.

Văn phạm đã cho có các luật sinh là S->aSbb và S->abb. Để xác định lớp của văn phạm, ta cần xem xét các ràng buộc của từng lớp văn phạm theo phân cấp Chomsky:

- Văn phạm lớp 0 (Unrestricted Grammar): Không có ràng buộc nào.

- Văn phạm lớp 1 (Context-Sensitive Grammar): Các luật sinh có dạng α -> β, trong đó |α| ≤ |β| (độ dài của α không lớn hơn độ dài của β), ngoại trừ luật S -> ε nếu S không xuất hiện ở vế phải của bất kỳ luật nào.

- Văn phạm lớp 2 (Context-Free Grammar): Các luật sinh có dạng A -> γ, trong đó A là một biến duy nhất.

- Văn phạm lớp 3 (Regular Grammar): Các luật sinh có dạng A -> aB hoặc A -> a, trong đó A và B là các biến, và a là một terminal.

Trong trường hợp này:

- Luật S -> aSbb vi phạm ràng buộc của văn phạm lớp 2 và lớp 3 vì vế phải chứa nhiều hơn một ký hiệu không kết thúc (S và b).

- Xét luật S -> aSbb, độ dài vế trái là 1, độ dài vế phải là 4. Luật S -> abb, độ dài vế trái là 1, độ dài vế phải là 3. Vì vậy, cả hai luật đều thỏa mãn điều kiện |α| ≤ |β| của văn phạm lớp 1.

Vì văn phạm không phải là lớp 2 hoặc lớp 3, nhưng thỏa mãn điều kiện của lớp 1, nên nó là văn phạm lớp 1.

Biểu thức chính quy x/y ký hiệu cho tập hợp chứa chuỗi x theo sau là chuỗi y. Do đó, nó biểu diễn tập hợp {xy}.

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