Văn phạm gồm các luật sinh A->Bx; A->x là văn phạm?

Tuyến tính phải

Tuyến tính trái

Không phải là tuyến tính phải và trái

Tuyến tính phải và trái

Trả lời:

Đáp án đúng: B

Văn phạm được gọi là tuyến tính phải nếu mọi luật sinh đều có dạng A → xB hoặc A → x, trong đó A, B là các biến (non-terminal) và x là một chuỗi các ký tự kết thúc (terminal). Dựa trên định nghĩa này, văn phạm với các luật sinh A → Bx và A → x không phải là tuyến tính phải vì luật A → Bx có B ở vị trí đầu tiên (tức bên trái) thay vì ở cuối (bên phải). Tuy nhiên, nó cũng không phải tuyến tính trái vì luật A -> Bx có x ở bên phải B. Do đó, đáp án chính xác là "Không phải là tuyến tính phải và trái".

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

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?

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

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: