Mối quan hệ giữa ngôn ngữ được chấp nhận NFA và ngôn ngữ được chấp nhận DFA

Trả lời:

Đáp án đúng: C

Giải thích:

Mối quan hệ giữa ngôn ngữ được chấp nhận bởi NFA (Non-deterministic Finite Automaton) và DFA (Deterministic Finite Automaton) là bằng nhau. Điều này có nghĩa là, đối với bất kỳ ngôn ngữ nào có thể được chấp nhận bởi một NFA, luôn tồn tại một DFA chấp nhận ngôn ngữ đó, và ngược lại. Do đó, khả năng biểu diễn ngôn ngữ của hai loại máy này là tương đương nhau.

Đáp án C (=) thể hiện chính xác mối quan hệ này.

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

Văn phạm gồm các luật sinh S ->abS; S->a được gọi là

Lời giải:

Đáp án đúng: A

Văn phạm tuyến tính phải là văn phạm mà trong các luật sinh, vế phải chứa tối đa một ký hiệu không kết thúc và ký hiệu này nằm ở vị trí cuối cùng. Trong văn phạm đã cho, luật sinh S -> abS có ký hiệu không kết thúc S ở cuối vế phải. Luật sinh S -> a chỉ chứa ký hiệu kết thúc. Do đó, văn phạm này là văn phạm tuyến tính phải.

Văn phạm tuyến tính trái là văn phạm mà trong các luật sinh, vế phải chứa tối đa một ký hiệu không kết thúc và ký hiệu này nằm ở vị trí đầu tiên. Văn phạm đã cho không thỏa mãn điều kiện này vì trong luật sinh S -> abS, ký hiệu không kết thúc S không nằm ở vị trí đầu tiên.

Vì vậy, đáp án đúng là văn phạm tuyến tính phải.

Câu 26:

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

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

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: