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

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:

Đáp án đúng: C

Câu hỏi này liên quan đến việc xây dựng bảng phân tích LR(0) cho một văn phạm. Cụ thể, nó yêu cầu tính Goto(I0, S), tức là trạng thái mới của tập mục khi đọc ký hiệu S từ trạng thái I0. Để giải quyết, ta cần xác định I0 (tập mục khởi đầu) trước. I0 chứa luật sinh gốc (S' -> .S) và closure của nó. Closure bao gồm tất cả các luật sinh có vế phải bắt đầu bằng một non-terminal có mặt sau dấu chấm trong một luật sinh khác. Trong trường hợp này, I0 sẽ chứa S' -> .S, S -> .AS, S -> .b, A -> .SA và A -> .a. Goto(I0, S) là tập hợp các luật sinh có dạng X -> S.Y, với X -> .SY thuộc I0, sau đó tính closure của tập hợp này. Từ I0, ta thấy các luật sinh S' -> .S và A -> .SA có S sau dấu chấm. - Khi đọc S từ S' -> .S, ta được S' -> S. - Khi đọc S từ A -> .SA, ta được A -> S.A. Vậy, tập hợp ban đầu là {S' -> S., A -> S.A}. Ta cần tính closure của tập hợp này. Closure của A -> S.A bao gồm việc thêm tất cả các luật sinh có A ở vế trái, với dấu chấm ở đầu vế phải: A -> .SA và A -> .a. Do đó, Goto(I0, S) = {S' -> S., A -> S.A, A -> .SA, A -> .a}. Đáp án C: {S' -> S., A -> S.A, A -> .a} là gần đúng nhất, nhưng thiếu A -> .SA Đáp án B: {A -> S.A, S -> .b} là sai. Đáp án A: {S' -> S, A -> .a} là sai. Đáp án D: {S -> .b , A -> .a} là sai. Vì không có đáp án nào hoàn toàn chính xác, ta chọn đáp án gần đúng nhất là C, nhưng cần lưu ý rằng nó thiếu A -> .SA.

Câu 37:

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

Lời giải: