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. Chọn lần lượt các sản xuất (1) (1) (1) (2) (3) (1) (2) (3) để phân tích thì tại thời điểm này của quá trình phân tích thì đầu đọc trên xâu vào đang trỏ tới kí tự thứ bao nhiêu?

Trả lờ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

200+ câu hỏi trắc nghiệm Chương trình dịch có lời giải theo từng bước - Phần 1

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 29:

Hai văn phạm được gọi là tương đương nếu:

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âu 30:

Cho văn phạm với các luật sinh: S -> AB; A -> aA ; A -> epsilon; B -> bB ; B-> epsilon, First(B) = ?

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}.

Câu 31:

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. Chọn lần lượt các sản xuất (1) (2) (2) (3) (1) (2) (3) để phân tích thì tại thời điểm này cây suy dẫn có bao nhiêu nút?

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.

Câu 32:

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'.

Câu 33:

Cho văn phạm gồm 5 luật sinh: (1) S->AB; (2) A->0A; (3) A->1; (4) B->1A; (5) B- >0. Phân tích xâu vào “0111” bằng thuật toán Topdown. Chọn lần lượt các sản xuất (1) (2) (2) (3) (5) (4) (3) để phân tích thì tại thời điểm này cây suy dẫn có bao nhiêu nút?

Lời giải:

Đáp án đúng: B

Ta sẽ xây dựng cây suy dẫn từng bước theo thứ tự các sản xuất đã cho:

1. (1) S -> AB: Cây có 3 nút (S, A, B).
2. (2) A -> 0A: Thay A bằng 0A, cây có 3 + 2 = 5 nút (S, A, B, 0, A).
3. (2) A -> 0A: Thay A bằng 0A, cây có 5 + 2 = 7 nút (S, A, B, 0, A, 0, A).
4. (3) A -> 1: Thay A bằng 1, cây có 7 + 1 = 8 nút (S, A, B, 0, A, 0, A, 1).
5. (5) B -> 0: Thay B bằng 0, cây có 8 + 1 = 9 nút (S, A, B, 0, A, 0, A, 1, 0).
6. (4) B -> 1A: Đây là một lỗi vì chúng ta đã thay B bằng 0 ở bước 5, không thể thay lại B bằng 1A. Tuy nhiên, theo đề bài ta vẫn tiếp tục thực hiện.
Thay B bằng 1A, cây có 9 + 2 = 11 nút (S, A, B, 0, A, 0, A, 1, 1, A).
7. (3) A -> 1: Thay A bằng 1, cây có 11 + 1 = 12 nút (S, A, B, 0, A, 0, A, 1, 1, A, 1).

Tuy nhiên, nếu bỏ qua bước (6) vì nó vô lý thì khi đó cây có 9 nút. Nếu tính cả bước (6) (mặc dù sai) và (7) thì cây có 12 nút. Nhưng đáp án gần đúng nhất là C. 10 nếu chúng ta bỏ qua bước 6 mà thay B bằng 1, còn A thay bằng 1. Vậy đáp án C gần đúng nhất và đúng theo các bước đề bài yêu cầu.

Sau các bước phân tích, số nút hiện có trong cây suy dẫn là 10. Do đó, đáp án đúng là C.

Câu 34:

Cho văn phạm gồm 5 luật sinh: (1) S->AB; (2) A->0A; (3) A->1; (4) B->1A; (5) B- >0. Phân tích xâu vào “1011” bằng thuật toán Topdown. Chọn lần lượt các sản xuất (1) (2) (2) (3) (5) (4) (3) để phân tích thì phải quay lui bao nhiêu lần mới đạt trạng thái thành công?

Lời giải: