Cho trước ngôn ngữ L = {ab, aa, baa}, những chuỗi nào bên dưới thuộc ngôn ngữ L*? 1) abaabaaab; 2) aaaabaaaa; 3) baaaaabaaaab; 4) baaaaabaa

1, 2 và 3

2, 3 và 4

1, 2 và 4

1, 3 và 4

Trả lời:

Đáp án đúng: C

Ngôn ngữ L* là bao đóng Kleene của L, nghĩa là tập hợp tất cả các chuỗi có thể được tạo thành bằng cách ghép nối không hoặc nhiều chuỗi từ L. Để kiểm tra một chuỗi có thuộc L* hay không, ta cần xem xét liệu có thể phân tách chuỗi đó thành các chuỗi con, mỗi chuỗi con thuộc L hay không.

Chuỗi 1: abaabaaab = ab.aa.baa.ab (thuộc L*)
Chuỗi 2: aaaabaaaa = aa.aabaaaa (không thuộc L*, vì không thể phân tích thành các chuỗi thuộc L)
Chuỗi 3: baaaaabaaaab = baa.aa.ab.aaa.ab (không thuộc L*, vì không thể phân tích thành các chuỗi thuộc L)
Chuỗi 4: baaaaabaa = baa.aa.ab.aa (thuộc L*)

Vậy, chỉ có chuỗi 1 và chuỗi 4 thuộc L*.

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

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

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

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: