Cho văn phạm G = {S->aSb; S->bSa; S->SS; S->a; S->epsilon} Chuỗi nào sau đây KHÔNG được sinh ra bởi G:

abbaab

baabab

abbaabb

babbaaa

Trả lời:

Đáp án đúng: C

Văn phạm G sinh ra các chuỗi có số lượng ký tự 'a' và 'b' bằng nhau. * **Đáp án A (abbaab):** Có 3 'a' và 3 'b'. Có thể sinh ra từ G. * **Đáp án B (baabab):** Có 3 'a' và 3 'b'. Có thể sinh ra từ G. * **Đáp án C (abbaabb):** Có 4 'a' và 3 'b'. Không thể sinh ra từ G. * **Đáp án D (babbaaa):** Có 3 'a' và 3 'b'. Có thể sinh ra từ G. Vậy, đáp án C là chuỗi KHÔNG được sinh ra bởi G.

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 2

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 31:

Cho văn phạm với các luật sinh: S->aAb; S->c; A->mSn. FOLLOW(S) =?

Lời giải:

Đáp án đúng: D

Để tìm FOLLOW(S), ta thực hiện theo các bước sau:

\r\n

\r\n
Bước 1: Đặt $ vào FOLLOW(S), trong đó S là ký hiệu bắt đầu.
\r\n
\r\n
Bước 2: Nếu có luật sinh A -> αBβ, thì mọi phần tử của FIRST(β) (ngoại trừ ε) được thêm vào FOLLOW(B).
\r\n
\r\n
Bước 3: Nếu có luật sinh A -> αB, hoặc A -> αBβ, trong đó FIRST(β) chứa ε, thì mọi phần tử của FOLLOW(A) được thêm vào FOLLOW(B).
\r\n

\r\n

Áp dụng vào văn phạm đã cho:

\r\n

\r\n
S là ký hiệu bắt đầu, nên $ ∈ FOLLOW(S)
\r\n
\r\n
Xét luật sinh S -> aAb. Ta thấy b theo sau A, nên FIRST(b) = {b} sẽ được thêm vào FOLLOW(A).
\r\n
\r\n
Xét luật sinh A -> mSn. Ta thấy n theo sau S, nên FIRST(n) = {n} sẽ được thêm vào FOLLOW(S).
\r\n
\r\n
Vậy FOLLOW(S) = {$, n}. Vì không có đáp án nào trùng khớp, nên câu hỏi không có đáp án đúng.
\r\n

Câu 32:

Cho văn phạm với các luật sinh: S->aAb; S->c; A->hSg. FIRST(S) =?

Lời giải:

Đáp án đúng: B

Để tìm FIRST(S), ta cần xem xét tất cả các luật sinh có S ở vế trái:

S -> aAb: Ký tự đầu tiên của vế phải là 'a'. Do đó, 'a' thuộc FIRST(S).
S -> c: Ký tự đầu tiên của vế phải là 'c'. Do đó, 'c' thuộc FIRST(S).

Vậy FIRST(S) = {a, c}.

Câu 33:

Cho văn phạm gồm 6 luật sinh: (1) S->AB; (2) A->A0; (3) A->B0; (4) A- >1; (5) B- >A1; (6) B->0. Phân tích xâu vào “1011” bằng thuật toán Bottom-up. Hành động của bộ phân tích lần lượt là: gạt, thu gọn theo (4), gạt, thu gọn theo (2), gạt, thu gọn theo (4), gạt, thu gọn theo (5) thì trạng thái phân tích tại thời điểm này là gì?

Lời giải:

Đáp án đúng: D

Phân tích xâu "1011" theo thuật toán Bottom-up với các bước đã cho:

1. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$` `1`, Xâu vào: `011$`
2. Thu gọn theo (4): A -> 1: Thay '1' trên ngăn xếp bằng 'A'. Ngăn xếp: `$` `A`, Xâu vào: `011$`
3. Gạt: Đọc '0' vào ngăn xếp. Ngăn xếp: `$` `A` `0`, Xâu vào: `11$`
4. Thu gọn theo (2): A -> A0: Thay 'A0' trên ngăn xếp bằng 'A'. Ngăn xếp: `$` `A`, Xâu vào: `11$`
5. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$` `A` `1`, Xâu vào: `1$`
6. Thu gọn theo (4): A -> 1: Thay '1' trên ngăn xếp bằng 'A'. Ngăn xếp: `$` `A` `A`, Xâu vào: `1$`
7. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$` `A` `A` `1`, Xâu vào: `$`
8. Thu gọn theo (5): B -> A1: Thay 'A1' trên ngăn xếp bằng 'B'. Ngăn xếp: `$` `A` `B`, Xâu vào: `$`. Trạng thái: $AB

Câu 34:

Cho văn phạm gồm 6 luật sinh: (1) S->AB; (2) A->A0; (3) A->B0; (4) A- >1; (5) B- >A1; (6) B->0. Phân tích xâu vào “1011” bằng thuật toán Bottom-up. Hành động của bộ phân tích lần lượt là: gạt, thu gọn theo (4), gạt, thu gọn theo (2), gạt, thu gọn theo (4), gạt, thu gọn theo (5), thu gọn (1) thì trạng thái phân tích tại thời điểm này là gì?

Lời giải:

Đáp án đúng: A

Phân tích xâu "1011" theo thuật toán Bottom-up:
1. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$1`, Xâu còn lại: `011$`
2. Thu gọn theo (4) A -> 1: Thay '1' bằng 'A'. Ngăn xếp: `$A`, Xâu còn lại: `011$`
3. Gạt: Đọc '0' vào ngăn xếp. Ngăn xếp: `$A0`, Xâu còn lại: `11$`
4. Thu gọn theo (2) A -> A0: Thay 'A0' bằng 'A'. Ngăn xếp: `$A`, Xâu còn lại: `11$`
5. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$A1`, Xâu còn lại: `1$`
6. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$A11`, Xâu còn lại: `$`
7. Thu gọn (4) A -> 1: Ngăn xếp: `$A1A`, Xâu còn lại: `$`
8. Thu gọn (5) B -> A1: Ngăn xếp: `$BA`, Xâu còn lại: `$`
9. Thu gọn (1) S -> AB: Khong the thu gon do B truoc A

Câu 35:

Cho văn phạm gồm 7 luật sinh: (1) S->BA; (2) C->A0; (3) A->1; (4) B->A1; (5) B- >0; (6) A-> epsilon; (7) B-> epsilon. FIRST (C)=?

Lời giải:

Đáp án đúng: D

Để tìm FIRST(C), ta cần xem xét các luật sinh có C ở vế trái, ở đây là luật C -> A0. Theo định nghĩa, FIRST(C) sẽ bao gồm FIRST(A0). Để tìm FIRST(A0), ta xét FIRST(A). Từ các luật sinh A -> 1 và A -> epsilon, ta có FIRST(A) = {1, epsilon}. Vì epsilon thuộc FIRST(A), ta cần xét đến phần tử tiếp theo sau A trong luật sinh C -> A0, đó là 0. Do đó, FIRST(A0) = {1} ∪ {0} = {0, 1}. Vậy FIRST(C) = {0, 1}.

Câu 36:

Trong phương pháp “Phân tích dự đoán không đệ qui” thì ký hiệu ‘dollar’ là

Lời giải: