Biểu thức chính quy là

Ngôn ngữ thuộc lớp 0

Ngôn ngữ thuộc lớp 1

Ngôn ngữ thuộc lớp 2

Ngôn ngữ thuộc lớp 3

Trả lời:

Đáp án đúng: A

Biểu thức chính quy (Regular Expression) tương ứng với ngôn ngữ thuộc lớp 3 trong hệ thống phân cấp Chomsky. Hệ thống phân cấp Chomsky phân loại các ngôn ngữ hình thức thành bốn loại: loại 0 (ngôn ngữ không hạn chế), loại 1 (ngôn ngữ ngữ cảnh phụ thuộc), loại 2 (ngôn ngữ phi ngữ cảnh) và loại 3 (ngôn ngữ chính quy). Các ngôn ngữ chính quy có thể được mô tả bằng các biểu thức chính quy hoặc các máy trạng thái hữu hạn (finite automata).

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

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

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

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: