Chuỗi nào không được sinh bởi văn phạm có luật sinh S- >SaSbS; S->epsilon

aabb

abab

aababb

aaabbb

Trả lời:

Đáp án đúng: B

Văn phạm S -> SaSbS; S -> epsilon sinh ra ngôn ngữ các chuỗi có dạng aⁿbⁿ. * **Đáp án A: aabb** có thể được sinh ra từ văn phạm: S -> SaSbS -> aaSbSbS -> aabb * **Đáp án B: abab** không thể được sinh ra từ văn phạm vì số lượng a và b bằng nhau, nhưng chúng không liền kề nhau theo đúng thứ tự. * **Đáp án C: aababb** không thể sinh ra, nó có 3 ký tự a và 3 ký tự b. Để có thể sinh ra chuỗi này thì chuỗi con aab phải đứng trước chuỗi con abb theo cấu trúc SaSbS. * **Đáp án D: aaabbb** có thể được sinh ra từ văn phạm: S -> SaSbS -> aaSbSbS -> aaaSbSbSbS -> aaabbb Vậy, đáp án đúng là B.

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

Văn phạm nào sau đây KHÔNG nhập nhằng:

Lời giải:

Đáp án đúng: B

Câu hỏi yêu cầu tìm văn phạm KHÔNG nhập nhằng.

* Văn phạm nhập nhằng (Ambiguous Grammar): Là văn phạm mà một chuỗi có thể có nhiều cây cú pháp (parse tree) khác nhau, hoặc có nhiều dẫn xuất bên trái (leftmost derivation) khác nhau.

Phân tích từng đáp án:

* A. S→ aSb; S->bSa; S-> SS; S->a: Văn phạm này nhập nhằng vì có thể tạo ra nhiều cây cú pháp cho cùng một chuỗi. Ví dụ, chuỗi "ababa" có thể được tạo ra bằng nhiều cách khác nhau sử dụng luật `S -> SS`.
* B. S → aSbS; S->bSaS; S->a; S->epsilon: Văn phạm này cũng nhập nhằng. Ví dụ, chuỗi "aa" có thể được dẫn xuất từ S -> aSaS -> a a hoặc một số cách khác.
* C. S→aS; S->aSb; S->b: Văn phạm này nhập nhằng. Ví dụ chuỗi `ab` có thể được tạo ra từ `S -> aS -> ab` hoặc `S -> aSb -> ab`. Thật ra văn phạm này sinh ra các chuỗi có dạng `a^n b^m` với n >= 1 và m <= 1.
* D. S→ aS; S->bS; S->epsilon: Văn phạm này KHÔNG nhập nhằng. Nó sinh ra các chuỗi các ký tự a và b bất kỳ theo thứ tự nào, bao gồm cả chuỗi rỗng. Mỗi chuỗi chỉ có một cây cú pháp duy nhất.

Vậy đáp án đúng là D.

Câu 28:

Cho văn phạm G, với S là ký hiệu bắt đầu, phân tích xâu vào theo phương pháp phân tích bottom-up, trạng thái thành công là:

Lời giải:

Đáp án đúng: A

Trong phương pháp phân tích bottom-up (từ dưới lên), chúng ta bắt đầu từ các ký hiệu cuối và cố gắng xây dựng cây phân tích ngược lên đến ký hiệu bắt đầu. Trạng thái thành công của quá trình phân tích là khi ngăn xếp chỉ chứa ký hiệu bắt đầu (S) được bao quanh bởi ký hiệu kết thúc chuỗi ($), và đầu vào cũng chỉ còn ký hiệu kết thúc chuỗi ($). Điều này có nghĩa là chúng ta đã giảm toàn bộ chuỗi đầu vào về ký hiệu bắt đầu của văn phạm.

Trong các lựa chọn:

A. ngăn xếp: dollar S, Đầu vào: dollar: Đây là trạng thái thành công, vì ngăn xếp chứa ký hiệu bắt đầu (S) và ký hiệu kết thúc ($), và đầu vào cũng chỉ còn ký hiệu kết thúc ($).
B. ngăn xếp: dollar, Đầu vào: dollar: Trạng thái này không cho biết chuỗi đã được rút gọn về ký hiệu bắt đầu.
C. ngăn xếp: dollar S, Đầu vào: S dollar: Đầu vào không đúng định dạng, vì S không nên xuất hiện trong đầu vào ở giai đoạn này.
D. ngăn xếp: dollar S, Đầu vào: a dollar: Đầu vào còn chứa ký hiệu 'a', nghĩa là chưa phân tích hết chuỗi.

Câu 29:

Cho văn phạm G gồm các luật sinh: E->EE*; E->EE+; E->a; E->b. Dạng câu thứ 5 (tính dạng câu đầu tiên là E) trong dãy dẫn xuất trái nhất của chuỗi abb++a* trong G là:

Lời giải:

Đáp án đúng: C

The grammar G has the following production rules: E->EE*; E->EE+; E->a; E->b. We want to find the 5th sentential form (starting with the initial E) in the leftmost derivation of the string "abb++a*".

1. E
2. EE+ (E -> EE+)
3. EEE++ (E -> EE+)
4. aEE++ (E -> a)
5. abE++ (E -> b)

So the 5th sentential form is abE++.

Câu 30:

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:

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

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: