ĐỀ KIỂM TRA MÔN: AUTOMAT
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (40.48 KB, 1 trang )
ĐỀ KIỂM TRA
MÔN: AUTOMAT
1) Tại sao gọi là automat hữu hạn đơn định (dfa)
2) Xây dựng automat hữu hạn không đơn định (nfa) đoán nhận ngôn ngữ gồm các xâu
trên bảng chữ {a, b} có độ dài chia hết cho 5.
3) Xây dựng dfa đoán nhận ngôn ngữ gồm các xây trên bảng chữ {0, 1} có số kí hiệu 0
bằng số kí hiệu 1
4) Chứng minh ngôn ngữ L={11w00|w∈{0,1}*} là chính qui
5) Tìm dfa tương đương với nfa sau:
b
Q
1
a
Q
0
ε
ε
a
b
Q
33
Q
2
6) Tìm biểu thức chính qui chỉ định ngôn ngữ gồm các xâu trên bảng chữ {a, b} có nhiều
nhất một cặp kí hiệu aa.
7) Tìm nfa tương ứng với biểu thức chính qui (ab+a)*aa(a+b)*
8) Tìm nfa tương ứng với văn phạm sau:
S → aSa|ab|ε
9) Tìm nfa tương ứng với văn phạm sau:
S → aA
A → baS|a
10) Cho ngôn ngữ L được chỉ định bởi biểu thức chính qui sau: (a+b)*aa hãy tìm nfa
đoán nhận ngôn ngữ nghịch đảo của L (mỗi câu tính 1 điểm)
