Trong biểu thức chính quy, toán tử * có chức năng:

Nối

Chọn

Lặp

Cộng

Trả lời:

Đáp án đúng: C

Trong biểu thức chính quy, toán tử * (dấu hoa thị) biểu thị sự lặp lại. Nó cho phép một ký tự hoặc một nhóm ký tự đứng trước nó xuất hiện không lần nào hoặc nhiều lần. Ví dụ, biểu thức chính quy a* sẽ khớp với "", "a", "aa", "aaa", v.v.

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

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

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

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: