Luật sinh A -> XYZ có thể tạo thành mấy mục?

Trả lời:

Đáp án đúng: D

Luật sinh A → XYZ tạo ra 3 mục, mỗi ký tự X, Y, và Z đại diện cho một mục riêng biệt. Do đó, đáp án đúng là C.

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 3

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 G gồm các luật sinh: E->EE*; E->EE+; E->a; E->b. Chuỗi nào sau đây được sinh ra bởi G

Lời giải:

Đáp án đúng: B

Văn phạm G cho phép tạo ra các biểu thức sử dụng toán tử * và + với các toán hạng a và b. Chúng ta cần kiểm tra chuỗi nào có thể được sinh ra từ văn phạm này.

* A. a++b*a: Chuỗi này không thể sinh ra từ G vì có hai toán tử + liền nhau. Văn phạm chỉ cho phép một toán tử giữa hai biểu thức E.
* B. aab++a: Chuỗi này có thể sinh ra từ G. Ta có thể phân tích như sau: E -> EE+ -> aE+ -> aaE++ -> aab++ -> aab++a (hoặc một cách khác, E -> EE+ -> EE+E -> aE+E -> aaE++E -> aab++E -> aab++a).
* C. a+bb*: Chuỗi này không thể sinh ra từ G vì toán tử + đứng trước hai toán hạng b liên tiếp mà không có biểu thức E nào khác ở giữa.
* D. ab*bb+: Chuỗi này không thể sinh ra từ G vì có hai toán hạng b liên tiếp sau toán tử *. Tương tự như trên, phải có biểu thức E ở giữa.

Vậy, đáp án đúng là B. aab++a.

Câu 32:

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

Lời giải:

Đáp án đúng: C

Văn phạm G sinh ra các chuỗi có dạng số lượng 'a' và 'b' bằng nhau, hoặc chuỗi rỗng (epsilon). Ta sẽ kiểm tra từng đáp án:

* A. abbaa: Số lượng 'a' là 3, số lượng 'b' là 2. Không thỏa mãn.
* B. aaba: Số lượng 'a' là 3, số lượng 'b' là 1. Không thỏa mãn.
* C. bbaaaa: Số lượng 'a' là 4, số lượng 'b' là 2. Không thỏa mãn.

Vì không có đáp án nào thỏa mãn điều kiện số lượng 'a' và 'b' bằng nhau, nên không có đáp án đúng.

Câu 33:

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. Từ gốc của cây, áp dụng suy dẫn (1) để triển khai, sau đó áp dụng suy dẫn (1) để triển khai bước sau thì cây suy dẫn tại thời điểm này có bao nhiêu nút?

Lời giải:

Đáp án đúng: D

Phân tích xâu "aacbc" bằng thuật toán Top-down, bắt đầu từ luật sinh S.

Bước 1: Áp dụng luật sinh (1) S -> aSbS. Cây suy dẫn hiện tại có dạng:

S
/|\
a S b S

Số nút hiện tại: 4

Bước 2: Tiếp tục áp dụng luật sinh (1) S -> aSbS vào nút S thứ nhất (từ trái sang). Cây suy dẫn trở thành:

S
/|\
a S b S
/|\
a S b S

Số nút hiện tại: 4 + 3 = 7 (Thêm 3 nút mới: a, S, b, S)

Vậy, sau khi áp dụng suy dẫn (1) hai lần liên tiếp, cây suy dẫn có 7 nút.

Câu 34:

Cho văn phạm gồm các luật sinh: S –> T * P; T –> U ; T->T * U; P –> Q + P ; P->Q; Q –> id; U –> id Phát biểu nào bên dưới đúng?

Lời giải:

Đáp án đúng: B

Phân tích văn phạm:

* `P -> Q + P | Q` cho thấy `+` là kết hợp phải vì `P` đệ quy ở bên phải của phép toán `+`. Điều này có nghĩa là biểu thức `a + b + c` sẽ được hiểu là `a + (b + c)`.
* `T -> T * U | U` cho thấy `*` là kết hợp trái vì `T` đệ quy ở bên trái của phép toán `*`. Điều này có nghĩa là biểu thức `a * b * c` sẽ được hiểu là `(a * b) * c`.

Vậy, đáp án đúng là: Toán tử + là kết hợp phải, trong khi * là kết hợp trái.

Câu 35:

Một ngôn ngữ được sinh ra bởi một văn phạm gọi là:

Lời giải:

Đáp án đúng: B

Văn phạm (Grammar) là một tập hợp các quy tắc được sử dụng để sinh ra một ngôn ngữ. Ngôn ngữ được sinh ra bởi một văn phạm được gọi là ngôn ngữ phi ngữ cảnh (Context-Free Language). Các ngôn ngữ lập trình, ngôn ngữ máy, và ngôn ngữ hợp ngữ đều có thể được mô tả bằng văn phạm, nhưng không phải văn phạm nào cũng sinh ra chúng. Ngôn ngữ phi ngữ cảnh là khái niệm bao quát nhất trong các lựa chọn này.

Câu 36:

Cho văn phạm với các luật sinh: S->AS, S->b, A->SA, A->a. Kí hiệu I0 là tập mục đầu tiên của văn phạm, phép toán Goto(I0,S) =?

Lời giải: