Cho văn phạm gồm 3 luật sinh: (1) S->aSbS; (2) S->aS; (3) S->c. Phân tích xâu vào “aacbc” bằng thuật toán Top-down. Cây suy dẫn tại thời điểm bắt đầu có bao nhiêu nút?
Trả lời:
Đáp án đúng: A
Thuật toán Top-down bắt đầu bằng ký hiệu bắt đầu của văn phạm (trong trường hợp này là S) làm nút gốc của cây suy dẫn. Do đó, tại thời điểm bắt đầu, cây suy dẫn chỉ có một nút duy nhất là S.
Câu hỏi liên quan
Lời giải:
Đáp án đúng: D
Ta thực hiện phân tích xâu "aacbc" theo thuật toán Top-down với các luật sinh được chọn như sau:
1. S -> aSbS: Xâu hiện tại: `aSbS`. Đọc `a`.
2. S -> aSbS: Xâu hiện tại: `aaSbSbS`. Đọc `a`.
3. S -> aSbS: Xâu hiện tại: `aaaSbSbSbS`. Đọc `a`.
4. S -> aS: Xâu hiện tại: `aaaaSbSbSbS`.
5. S -> c: Xâu hiện tại: `aaaacSbSbSbS`. Đọc `c`.
Như vậy, sau khi áp dụng 5 luật sinh theo thứ tự trên, ta đã đọc các ký tự `a`, `a`, `a`, `c`. Do đó, đầu đọc đang trỏ tới ký tự thứ 5 của xâu vào (ký tự `b`).
Các bước tiếp theo:
6. S -> aSbS: Xâu hiện tại: `aaaac aSbSbSbS`
7. S -> aS: Xâu hiện tại `aaaac aaSbSbSbS`
8. S -> c: Xâu hiện tại: `aaaac aacSbSbSbS`. Đọc `c`.
Vậy đáp án đúng là C. 5
1. S -> aSbS: Xâu hiện tại: `aSbS`. Đọc `a`.
2. S -> aSbS: Xâu hiện tại: `aaSbSbS`. Đọc `a`.
3. S -> aSbS: Xâu hiện tại: `aaaSbSbSbS`. Đọc `a`.
4. S -> aS: Xâu hiện tại: `aaaaSbSbSbS`.
5. S -> c: Xâu hiện tại: `aaaacSbSbSbS`. Đọc `c`.
Như vậy, sau khi áp dụng 5 luật sinh theo thứ tự trên, ta đã đọc các ký tự `a`, `a`, `a`, `c`. Do đó, đầu đọc đang trỏ tới ký tự thứ 5 của xâu vào (ký tự `b`).
Các bước tiếp theo:
6. S -> aSbS: Xâu hiện tại: `aaaac aSbSbSbS`
7. S -> aS: Xâu hiện tại `aaaac aaSbSbSbS`
8. S -> c: Xâu hiện tại: `aaaac aacSbSbSbS`. Đọc `c`.
Vậy đáp án đúng là C. 5
Lời giải:
Đáp án đúng: A
Hai văn phạm được gọi là tương đương nếu chúng sinh ra cùng một ngôn ngữ. Điều này có nghĩa là chúng có thể có các quy tắc sinh khác nhau, nhưng tập hợp các chuỗi mà chúng tạo ra là giống hệt nhau.
Các lựa chọn khác không đúng vì:
* B. Cùng là văn phạm phi ngữ cảnh: Tính chất phi ngữ cảnh không đảm bảo tương đương.
* C. Cùng có số luật sinh bằng nhau: Số lượng luật sinh không ảnh hưởng đến việc văn phạm có tương đương hay không.
* D. Cùng là văn phạm mơ hồ: Tính mơ hồ của văn phạm không liên quan đến tính tương đương.
Các lựa chọn khác không đúng vì:
* B. Cùng là văn phạm phi ngữ cảnh: Tính chất phi ngữ cảnh không đảm bảo tương đương.
* C. Cùng có số luật sinh bằng nhau: Số lượng luật sinh không ảnh hưởng đến việc văn phạm có tương đương hay không.
* D. Cùng là văn phạm mơ hồ: Tính mơ hồ của văn phạm không liên quan đến tính tương đương.
Lời giải:
Đáp án đúng: D
Để tìm First(B), ta xét các luật sinh của B: B -> bB và B -> epsilon. Theo định nghĩa, First(B) là tập hợp các terminal có thể xuất hiện đầu tiên trong các chuỗi dẫn xuất từ B. Vì B có thể sinh ra 'bB', nên 'b' thuộc First(B). Vì B cũng có thể sinh ra 'epsilon' (chuỗi rỗng), nên 'epsilon' cũng thuộc First(B). Vậy, First(B) = {b, epsilon}.
Lời giải:
Đáp án đúng: D
Để giải bài này, ta sẽ thực hiện phân tích xâu "aacbc" theo thuật toán Top-down với các luật sinh được cho và đếm số nút trên cây suy dẫn tại thời điểm chỉ định. Các bước phân tích như sau:
1. S -> aSbS (1): Cây có 3 nút (S, a, SbS)
2. S -> aS (2): Thay S bằng aS trong SbS. Cây có thêm 2 nút (S, aS) -> Tổng: 5 nút.
3. S -> aS (2): Thay S bằng aS trong aS. Cây có thêm 2 nút (S, aS) -> Tổng: 7 nút.
4. S -> c (3): Thay S bằng c trong aS. Cây có thêm 1 nút (c) -> Tổng: 8 nút.
Vậy, sau 4 bước cây suy dẫn có 8 nút. Các luật sinh tiếp theo sẽ chỉ làm tăng số nút của cây.
5. S -> aSbS (1) Thay S bằng aSbS vào cây hiện tại: Cây có thêm 3 nút (S, a, SbS) -> Tổng: 11 nút
6. S -> aS (2): Thay S bằng aS trong SbS. Cây có thêm 2 nút (S, aS) -> Tổng: 13 nút.
7. S -> c (3): Thay S bằng c trong aS. Cây có thêm 1 nút (c) -> Tổng: 14 nút.
Tuy nhiên câu hỏi chỉ hỏi sau các bước 1, 2, 2, 3. Do đó đáp án là 8.
1. S -> aSbS (1): Cây có 3 nút (S, a, SbS)
2. S -> aS (2): Thay S bằng aS trong SbS. Cây có thêm 2 nút (S, aS) -> Tổng: 5 nút.
3. S -> aS (2): Thay S bằng aS trong aS. Cây có thêm 2 nút (S, aS) -> Tổng: 7 nút.
4. S -> c (3): Thay S bằng c trong aS. Cây có thêm 1 nút (c) -> Tổng: 8 nút.
Vậy, sau 4 bước cây suy dẫn có 8 nút. Các luật sinh tiếp theo sẽ chỉ làm tăng số nút của cây.
5. S -> aSbS (1) Thay S bằng aSbS vào cây hiện tại: Cây có thêm 3 nút (S, a, SbS) -> Tổng: 11 nút
6. S -> aS (2): Thay S bằng aS trong SbS. Cây có thêm 2 nút (S, aS) -> Tổng: 13 nút.
7. S -> c (3): Thay S bằng c trong aS. Cây có thêm 1 nút (c) -> Tổng: 14 nút.
Tuy nhiên câu hỏi chỉ hỏi sau các bước 1, 2, 2, 3. Do đó đáp án là 8.
Lời giải:
Đáp án đúng: D
Ta thực hiện phân tích xâu "aacbc" theo thuật toán Top-down và các luật sinh được chọn như sau:
1. S -> aSbS
- Xâu hiện tại: `aSbS`
2. S -> aS
- Xâu hiện tại: `a(aS)bS` tức là `aaSbS`
3. S -> aS
- Xâu hiện tại: `aa(aS)bS` tức là `aaaSbS`
4. S -> c
- Xâu hiện tại: `aa(c)bS` tức là `aacbS`
5. S -> aSbS
- Xâu hiện tại: `aacb(aSbS)` tức là `aacbaSbS`
6. S -> aS
- Xâu hiện tại: `aacba(aS)bS` tức là `aacbaaSbS`
7. S -> c
- Xâu hiện tại: `aacba(c)bS` tức là `aacbacbS`
Như vậy, sau 7 bước, ta có xâu `aacbacbS`. Khi so khớp với xâu vào `aacbc`, ta thấy `aacbacbS` khác với `aacbc`. Tuy nhiên, câu hỏi yêu cầu xác định vị trí đầu đọc trên xâu vào `aacbc` tại thời điểm này. Các luật sinh đã được áp dụng để tạo ra `aacb`.
Xâu vào là `aacbc`. Sau 4 bước, `aacb` đã được tạo ra. Khi áp dụng luật (1) S->aSbS ta được `aacbaSbS`. Như vậy khi so khớp đến đây, đầu đọc đã đọc đến ký tự thứ 5, tức là ký tự `c` trong xâu `aacbc`.
Do đó, đầu đọc đang trỏ tới ký tự 'c'.
1. S -> aSbS
- Xâu hiện tại: `aSbS`
2. S -> aS
- Xâu hiện tại: `a(aS)bS` tức là `aaSbS`
3. S -> aS
- Xâu hiện tại: `aa(aS)bS` tức là `aaaSbS`
4. S -> c
- Xâu hiện tại: `aa(c)bS` tức là `aacbS`
5. S -> aSbS
- Xâu hiện tại: `aacb(aSbS)` tức là `aacbaSbS`
6. S -> aS
- Xâu hiện tại: `aacba(aS)bS` tức là `aacbaaSbS`
7. S -> c
- Xâu hiện tại: `aacba(c)bS` tức là `aacbacbS`
Như vậy, sau 7 bước, ta có xâu `aacbacbS`. Khi so khớp với xâu vào `aacbc`, ta thấy `aacbacbS` khác với `aacbc`. Tuy nhiên, câu hỏi yêu cầu xác định vị trí đầu đọc trên xâu vào `aacbc` tại thời điểm này. Các luật sinh đã được áp dụng để tạo ra `aacb`.
Xâu vào là `aacbc`. Sau 4 bước, `aacb` đã được tạo ra. Khi áp dụng luật (1) S->aSbS ta được `aacbaSbS`. Như vậy khi so khớp đến đây, đầu đọc đã đọc đến ký tự thứ 5, tức là ký tự `c` trong xâu `aacbc`.
Do đó, đầu đọc đang trỏ tới ký tự '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