Văn phạm gồm các luật sinh: S->bA; S->aB; A->a B->b; A->aS B- >bS; A->bAA B- >aBB sinh ra được chuỗi nào?

aaaabb

aabbbb

aabbab

abbbba

Trả lời:

Đáp án đúng: C

The grammar generates strings of the form a^n b^m or b^n a^m, where n, m >= 1. Let's examine the options. None of the provided options can be generated by this grammar because it needs to have an equal or almost equal number of a's and b's.

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 29:

Cho văn phạm G = {S ->aAAB; S->bC; A-> bB; A-> epsilon; B-> Aa; B->A; B- >epsilon; C ->bA; C->B} Sau khi loại bỏ các sản xuất rỗng trong G, có bao nhiêu luật sinh có vế trái là S

Lời giải:

Đáp án đúng: A

Để loại bỏ các sản xuất rỗng trong văn phạm G, ta thực hiện các bước sau:

1. Tìm các biến có thể dẫn đến rỗng (epsilon):
- Từ A -> epsilon, B -> epsilon, ta có A và B có thể dẫn đến rỗng.

2. Loại bỏ các sản xuất rỗng:
- Thay thế các luật sinh có A hoặc B ở vế phải bằng các luật sinh mới, trong đó A hoặc B có thể có hoặc không.

Áp dụng vào văn phạm G:

G = {S -> aAAB; S -> bC; A -> bB; A -> epsilon; B -> Aa; B -> A; B -> epsilon; C -> bA; C -> B}

- S -> aAAB:
A và B có thể rỗng, nên ta có các luật sinh mới:
- S -> aAAB
- S -> aAA
- S -> aAB
- S -> aA
- S -> aB
- S -> a
- S -> aBB
- S -> aB (trùng với S -> aB, bỏ qua)
- S -> bC: Giữ nguyên (S -> bC)

Vậy các luật sinh có vế trái là S sau khi loại bỏ sản xuất rỗng là:

S -> aAAB
S -> aAA
S -> aAB
S -> aA
S -> aB
S -> a
S -> aBB
S -> bC

Có tổng cộng 8 luật sinh có vế trái là S.

Câu 30:

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

Lời giả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.

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: