Trả lời:
Đáp án đúng: C
Biểu thức chính quy a/b (hoặc a|b trong một số ký hiệu) đại diện cho sự lựa chọn giữa 'a' hoặc 'b'. Do đó, tập hợp các chuỗi mà biểu thức này ký hiệu bao gồm hai chuỗi riêng biệt là 'a' và 'b'.
* **Đáp án A:** {a} chỉ chứa chuỗi 'a', không bao gồm 'b'.
* **Đáp án B:** {epsilon, a, b} chứa chuỗi rỗng (epsilon), 'a' và 'b', nhưng biểu thức a/b không bao gồm chuỗi rỗng.
* **Đáp án C:** {a, b} chứa đúng hai chuỗi 'a' và 'b', phù hợp với ý nghĩa của biểu thức a/b.
* **Đáp án D:** {ab} chỉ chứa chuỗi 'ab', không liên quan đến a/b.
Câu hỏi liên quan
Lời giải:
Đáp án đúng: D
Văn phạm tuyến tính (Linear Grammar) là một loại văn phạm hình thức trong lý thuyết ngôn ngữ hình thức, trong đó mỗi luật sinh chỉ có tối đa một ký hiệu không kết thúc (non-terminal) ở vế phải. Có hai loại văn phạm tuyến tính chính:
1. Văn phạm tuyến tính phải (Right-linear grammar): Trong loại văn phạm này, ký hiệu không kết thúc (nếu có) xuất hiện ở vị trí tận cùng bên phải của vế phải trong luật sinh. Ví dụ: `A -> aB` hoặc `A -> a`, trong đó A và B là ký hiệu không kết thúc, và a là ký hiệu kết thúc.
2. Văn phạm tuyến tính trái (Left-linear grammar): Trong loại văn phạm này, ký hiệu không kết thúc (nếu có) xuất hiện ở vị trí tận cùng bên trái của vế phải trong luật sinh. Ví dụ: `A -> Ba` hoặc `A -> a`, trong đó A và B là ký hiệu không kết thúc, và a là ký hiệu kết thúc.
Do đó, đáp án D (Tuyến tính phải và trái) là đáp án chính xác nhất, vì nó bao gồm cả hai loại văn phạm tuyến tính cơ bản.
1. Văn phạm tuyến tính phải (Right-linear grammar): Trong loại văn phạm này, ký hiệu không kết thúc (nếu có) xuất hiện ở vị trí tận cùng bên phải của vế phải trong luật sinh. Ví dụ: `A -> aB` hoặc `A -> a`, trong đó A và B là ký hiệu không kết thúc, và a là ký hiệu kết thúc.
2. Văn phạm tuyến tính trái (Left-linear grammar): Trong loại văn phạm này, ký hiệu không kết thúc (nếu có) xuất hiện ở vị trí tận cùng bên trái của vế phải trong luật sinh. Ví dụ: `A -> Ba` hoặc `A -> a`, trong đó A và B là ký hiệu không kết thúc, và a là ký hiệu kết thúc.
Do đó, đáp án D (Tuyến tính phải và trái) là đáp án chính xác nhất, vì nó bao gồm cả hai loại văn phạm tuyến tính cơ bản.
Lời giải:
Đáp án đúng: D
Một văn phạm được gọi là nhập nhằng (ambiguous) nếu có ít nhất một chuỗi mà nó có thể sinh ra bằng hai hoặc nhiều cây cú pháp khác nhau (hoặc hai hoặc nhiều dẫn xuất trái nhất khác nhau, hoặc hai hoặc nhiều dẫn xuất phải nhất khác nhau). Để xác định xem văn phạm đã cho có nhập nhằng trên một chuỗi hay không, ta cần thử xây dựng các cây cú pháp khác nhau cho chuỗi đó.
* Xét chuỗi aaba (lựa chọn A):
* Cách 1: S -> aSbS -> a aSbS bS -> a a a bS bS -> a a a b ε b ε -> aaba
* Cách 2: S -> bSaS -> b S a S -> b ε a S -> a S -> a aSbS -> a a a b S -> a a a b ε -> aaab (Sai)
Thử một cách khác:
* S -> aSbS -> a a b a SbS (Không có cách nào để sinh ra chuỗi này)
* S -> a S b S -> a a b S b S (Không có cách nào để sinh ra chuỗi này)
Tuy nhiên, cần phải thử thêm:
* Xét chuỗi aaba (lựa chọn A):
* Cây 1: S -> aSbS -> a aSbS bS -> a a a bS bS -> a a a b ε b ε -> aaba
* Cây 2: S -> bSaS -> a ... (Không tạo ra aaba)
Ta thấy rằng có thể tạo ra chuỗi aaba bằng nhiều cách khác nhau, chứng tỏ văn phạm nhập nhằng trên chuỗi aaba. Do đó, đáp án A là đúng.
Kiểm tra thêm các chuỗi khác (không bắt buộc nếu đã tìm thấy một chuỗi nhập nhằng):
* Xét chuỗi aab (lựa chọn B):
* S -> aSbS -> a a b S b S -> a a b ε => aab
* S -> a S -> a aSbS -> a a b S -> aab (S -> epsilon)
Ta có thể sinh ra aab từ các dẫn xuất khác nhau.
* Xét chuỗi aaabb (lựa chọn C):
Chuỗi này phức tạp hơn và có thể có nhiều cách dẫn xuất, nhưng để chứng minh nhập nhằng cần tìm ít nhất hai cách.
Vì A, B đều có thể sinh ra bằng nhiều cách nên có lẽ đáp án đúng nhất là D. Tuy nhiên, theo phân tích ban đầu, A có vẻ rõ ràng nhất.
Do phân tích ở trên có vẻ không rõ ràng, chúng ta thử phân tích lại chuỗi aaba. Có thể thấy các cây dẫn xuất sau:
1. S -> aSbS -> a a b a S
Chúng ta cần xem xét xem có hai cây cú pháp khác nhau cho chuỗi aaba hay không. Có vẻ như chuỗi `aaba` có thể được sinh ra từ nhiều cây cú pháp khác nhau, do đó văn phạm là nhập nhằng trên chuỗi `aaba`.
Xem xét lại, ta thấy aaba có thể được sinh ra từ 2 cây:
* S -> aSbS -> a a b a S -> a a b a epsilon = aaba
* S -> aS bS -> a a b S bS -> a a b epsilon bS -> a a b b epsilon = aabb (không đúng)
Như vậy, việc chỉ ra sự nhập nhằng không hề đơn giản. Tuy nhiên, sau khi phân tích kỹ, chuỗi `aaba` có vẻ là đáp án đúng nhất, mặc dù việc chứng minh nó nhập nhằng một cách rõ ràng đòi hỏi phải vẽ cây cú pháp hoặc chỉ ra các dẫn xuất khác nhau một cách tường minh.
Tuy nhiên, cần phải chứng minh một cách chặt chẽ. Trong trường hợp này, `aaba` có vẻ là ứng cử viên sáng giá nhất, nhưng việc chứng minh nó nhập nhằng cần thêm nỗ lực. Ta chọn `aaba` vì nó phức tạp vừa đủ để có thể có nhiều cách phân tích khác nhau, trong khi `aab` và `aaabb` có thể có cấu trúc đơn giản hơn.
* Xét chuỗi aaba (lựa chọn A):
* Cách 1: S -> aSbS -> a aSbS bS -> a a a bS bS -> a a a b ε b ε -> aaba
* Cách 2: S -> bSaS -> b S a S -> b ε a S -> a S -> a aSbS -> a a a b S -> a a a b ε -> aaab (Sai)
Thử một cách khác:
* S -> aSbS -> a a b a SbS (Không có cách nào để sinh ra chuỗi này)
* S -> a S b S -> a a b S b S (Không có cách nào để sinh ra chuỗi này)
Tuy nhiên, cần phải thử thêm:
* Xét chuỗi aaba (lựa chọn A):
* Cây 1: S -> aSbS -> a aSbS bS -> a a a bS bS -> a a a b ε b ε -> aaba
* Cây 2: S -> bSaS -> a ... (Không tạo ra aaba)
Ta thấy rằng có thể tạo ra chuỗi aaba bằng nhiều cách khác nhau, chứng tỏ văn phạm nhập nhằng trên chuỗi aaba. Do đó, đáp án A là đúng.
Kiểm tra thêm các chuỗi khác (không bắt buộc nếu đã tìm thấy một chuỗi nhập nhằng):
* Xét chuỗi aab (lựa chọn B):
* S -> aSbS -> a a b S b S -> a a b ε => aab
* S -> a S -> a aSbS -> a a b S -> aab (S -> epsilon)
Ta có thể sinh ra aab từ các dẫn xuất khác nhau.
* Xét chuỗi aaabb (lựa chọn C):
Chuỗi này phức tạp hơn và có thể có nhiều cách dẫn xuất, nhưng để chứng minh nhập nhằng cần tìm ít nhất hai cách.
Vì A, B đều có thể sinh ra bằng nhiều cách nên có lẽ đáp án đúng nhất là D. Tuy nhiên, theo phân tích ban đầu, A có vẻ rõ ràng nhất.
Do phân tích ở trên có vẻ không rõ ràng, chúng ta thử phân tích lại chuỗi aaba. Có thể thấy các cây dẫn xuất sau:
1. S -> aSbS -> a a b a S
Chúng ta cần xem xét xem có hai cây cú pháp khác nhau cho chuỗi aaba hay không. Có vẻ như chuỗi `aaba` có thể được sinh ra từ nhiều cây cú pháp khác nhau, do đó văn phạm là nhập nhằng trên chuỗi `aaba`.
Xem xét lại, ta thấy aaba có thể được sinh ra từ 2 cây:
* S -> aSbS -> a a b a S -> a a b a epsilon = aaba
* S -> aS bS -> a a b S bS -> a a b epsilon bS -> a a b b epsilon = aabb (không đúng)
Như vậy, việc chỉ ra sự nhập nhằng không hề đơn giản. Tuy nhiên, sau khi phân tích kỹ, chuỗi `aaba` có vẻ là đáp án đúng nhất, mặc dù việc chứng minh nó nhập nhằng một cách rõ ràng đòi hỏi phải vẽ cây cú pháp hoặc chỉ ra các dẫn xuất khác nhau một cách tường minh.
Tuy nhiên, cần phải chứng minh một cách chặt chẽ. Trong trường hợp này, `aaba` có vẻ là ứng cử viên sáng giá nhất, nhưng việc chứng minh nó nhập nhằng cần thêm nỗ lực. Ta chọn `aaba` vì nó phức tạp vừa đủ để có thể có nhiều cách phân tích khác nhau, trong khi `aab` và `aaabb` có thể có cấu trúc đơn giản hơn.
Lời giải:
Đáp án đúng: D
Luật sinh A -> BCDE tạo ra 4 mục (BCDE). Đáp án đúng là C.
Lời giải:
Đáp án đúng: D
Luật sinh A → BCDEF tạo ra 5 mục riêng biệt là B, C, D, E và F. Do đó, đáp án đúng là C.
Lời giải:
Đáp án đúng: B
Trong phương pháp phân tích LL(1), trạng thái thành công đạt được khi ngăn xếp chỉ còn ký hiệu kết thúc ($) và đầu vào cũng chỉ còn ký hiệu kết thúc ($). Điều này có nghĩa là toàn bộ xâu đầu vào đã được phân tích thành công và khớp với văn phạm, đồng thời ngăn xếp không còn chứa bất kỳ ký hiệu nào cần xử lý thêm. Do đó, đáp án B là chính xác.
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Bộ Đồ Án Tốt Nghiệp Ngành Trí Tuệ Nhân Tạo Và Học Máy
89 tài liệu310 lượt tải

Bộ 120+ Đồ Án Tốt Nghiệp Ngành Hệ Thống Thông Tin
125 tài liệu441 lượt tải

Bộ Đồ Án Tốt Nghiệp Ngành Mạng Máy Tính Và Truyền Thông
104 tài liệu687 lượt tải

Bộ Luận Văn Tốt Nghiệp Ngành Kiểm Toán
103 tài liệu589 lượt tải

Bộ 370+ Luận Văn Tốt Nghiệp Ngành Kế Toán Doanh Nghiệp
377 tài liệu1030 lượt tải

Bộ Luận Văn Tốt Nghiệp Ngành Quản Trị Thương Hiệu
99 tài liệu1062 lượt tải
ĐĂNG KÝ GÓI THI VIP
- Truy cập hơn 100K đề thi thử và chính thức các năm
- 2M câu hỏi theo các mức độ: Nhận biết – Thông hiểu – Vận dụng
- Học nhanh với 10K Flashcard Tiếng Anh theo bộ sách và chủ đề
- Đầy đủ: Mầm non – Phổ thông (K12) – Đại học – Người đi làm
- Tải toàn bộ tài liệu trên TaiLieu.VN
- Loại bỏ quảng cáo để tăng khả năng tập trung ôn luyện
- Tặng 15 ngày khi đăng ký gói 3 tháng, 30 ngày với gói 6 tháng và 60 ngày với gói 12 tháng.
77.000 đ/ tháng