TRƯỜNG ĐHBK TP. HCM
KHOA KH&KT MÁY TÍNH
ĐỀ THI CUỐI KỲ
Môn: Mô hình hóa toán học (CO2011)
Thời gian làm bài: 90 phút
(SV được sử dụng một tờ A4
chứa các ghi chú cần thiết)
Ngày thi: 03/01/2020
Họ &tên SV: MSSV:
(Kết quả thi sẽ được quy về thang điểm 10 dựa vào kết quả của sinh viên làm bài tốt nhất. Sinh viên
không được viết nháp vào đề và hãy chọn đáp án chính xác nhất cho mỗi câu hỏi trắc nghiệm và trả
lời vào trong phiếu.)
Câu 1. Luật đúng đắn toàn phần (total correctness) cho cấu trúc while được phát biểu như sau
A(|φ∧B∧0≤E=E0|)C(|ψ∧0≤E < E0|)
(|φ∧0≤E|)while B{C}(|ψ∧ ¬B|).
B(|ψ∧B∧0≤E=E0|)C(|ψ∧0≤E < E0|)
(|ψ∧0≤E|)while B{C}(|ψ∧ ¬B|).
C(|φ∧B∧0≤E|)C(|ψ∧0≤E|)
(|φ∧0≤E|)while B{C}(|ψ∧ ¬B|).
D(|ψ∧B∧0≤E|)C(|ψ∧0≤E|)
(|ψ∧0≤E|)while B{C}(|ψ∧ ¬B|).
Câu 2. Xét đoạn chương trình sau.
Nếu cho biết rằng hậu điều kiện (postcondition) của nó là {x=y}thì điều kiện nào sau
đây là tiền điều kiện (precondition) của nó?
A{x= 2y∧y < 2}.
B{x > 2y∧y= 2}.
C{x= 2y∧y > 2}.
D{x < 2y∧y > 2}.
Câu 3. Chọn phát biểu đúng.
AKhi đọc một sự kiện từ một trạng thái, NFA không xác định được chắc chắn trạng thái kế tiếp.
BNFA không xác định được chắc chắn trạng thái kế tiếp để đơn giản hóa hình vẽ.
CNFA thì số trạng thái không xác định còn DFA thì xác định được số trạng thái.
DTổng số trạng thái luôn rút giảm trong quá trình đơn định hóa từ một NFA sang DFA.
Trong các câu 4–7, xét automata hữu hạn trên tập ký tự {a, b}bên dưới đây.
012
345
aab
b
b ε
a
aa, ε
b
Câu 4. Hãy cho biết đâu không phải là từ hợp lệ trong automata trên.
Aabababa
Bbbbbbabaa
Caabbaabbababa
Daabbbbaa
Chữ ký SV:.................. Mã đề 1913 (B01) Trang 1
Câu 5. Hãy viết biểu thức chính qui cho automata bên trên.
AX=a∗ba∗;Y=b∗ab∗a;Z=X(Y(a+b)X)∗+XY ((a+b)XY )∗
BX=a∗ba∗b∗a;Y=b∗a;Z=X(Y(ab +b)X)∗+XY ((ab +b)XY )∗
CX=a∗b;Y=a∗b∗ab∗a;Z=X(Y(ab +b)X)∗+XY ((ab +b)XY )∗
DX=a∗b;Y=a∗+a∗b∗ab∗a;Z=X(Y(ab +b)X)∗+XY ((ab +b)XY )∗
Câu 6. Nếu sử dụng giải thuật đơn định hóa để chuyển NFA trên thành DFA thì DFA mới có bao nhiêu
trạng thái.
A20
B18
C15
D16
Câu 7. Số trạng thái có trong DFA tối giản (tương đương với NFA trên) là bao nhiêu?
A10
B20
C16
D18
Câu 8. Tiền điều kiện yếu nhất (weakest precondition) φcủa bộ ba Hoare
(|φ|)if (x < y) x = x + 3; else x = x + 1; (|x≤y|)
là
A(y > x)−→ (x+ 3 < y).
By≥x+ 3.
Cy≥x.
Dy≥x+ 1.
Câu 9. Tiền điều kiện yếu nhất (weakest precondition) φcủa bộ ba Hoare
(|φ|)x=1;y=x+y(|x≤y|)
là
Ay > x > 0.
By≥0.
Cy≥x≥0.
Dy > 0.
Câu 10. Biễu thức chính quy cho ngôn ngữ L={anbm|(n+m)chẵn}là
A((aa)+(bb)+)·(a(aa)+b(bb)+).
B(aa)∗(bb)∗+a(aa)∗b(bb)∗.
C((aa)∗(bb)∗)·(a(aa)∗b(bb)∗).
D(aa)+(bb)++a(aa)+b(bb)+.
Câu 11. Để xem xét automata bên dưới và biểu thức chính quy E= [(ab)∗(ba)∗(bb∗a(aa)∗b(ab)∗)∗]∗có
biểu diễn cùng một ngôn ngữ hay không, hãy chọn phát biểu đúng dưới đây.
q0
q1q2
q3
a
b
a
a
b
a
b
b
ABiểu diễn cùng một ngôn ngữ.
BKhông tương đương, tuy nhiên không thể xác định được phản ví dụ.
CKhông tương đương, phản ví dụ là aa.
DKhông tương đương, phản ví dụ là abbaaabab.
Chữ ký SV:.................. Mã đề 1913 (B01) Trang 2
Câu 12. Một dạng bất biến (invariant form) của chương trình downfac
mà ta có thể dùng trong việc chứng minh tính đúng đắn của nó là
A(y= (x−a)!) ∧(a≥0).
B(y=x!
a!)∧(a≥0).
C(y= (x−a)!) ∧(a≤x).
D(y=x!
a!)∧(a≤x).
Câu 13. Cho Plà chương trình x= 2020. Khi đó theo luật gán (assignment rule) ta có
A6|=par (|2020 = 4|)P(|x= 4|).
B|=tot (|2020 = 2020|)P(|x= 2020|).
C6|=par (|2020 = y|)P(|x=y|).
D6|=par (|2020 = 2020|)P(|x= 2020|).
Câu 14. Một dạng bất biến (invariant form) nên được sử dụng để chứng minh tính đúng đắn của đoạn
chương trình Pnhư trong Câu 30 là
A{m= (n−i)×n∧i≥0}.
B{m= (i×n)∧i > 0}.
C{m= (n−i)×n∧i > 0}.
D{m= (i×n)∧i > 0}.
Câu 15. Chuỗi nào dưới đây không thuộc vào ngôn ngữ L∗với Lđược biểu diễn bởi automata dưới đây.
A B C D
E F G
a
b
a a
b
a
b
b
a
b
a
Aaababba
Bbbaaaa
Caaaabb
Dabaababab
Câu 16. Luật đúng đắn (correctness) cho cấu trúc if... else được phát biểu như sau
A(|φ∧B|)C(|ψ|) (|φ∧ ¬B|)C(|ψ|)
(|φ|)if B{C} else { C}(|ψ|).
B(|φ1|)C1(|ψ|) (|φ2|)C2(|ψ|)
(|(B→φ1)∧(¬B→φ2)|)if B{C1} else { C2}(|ψ|).
C(|φ∧B|)C1(|ψ|) (|φ∧ ¬B|)C2(|ψ|)
(|φ|)if ¬B{C1} else { C2}(|ψ|).
D(|φ|)C1(|ψ|) (|φ|)C2(|ψ|)
(|(B→φ)∧(¬B→φ)|)if B{C1} else { C2}(|ψ|).
Chữ ký SV:.................. Mã đề 1913 (B01) Trang 3
Câu 17. Precondition của While
r:= 1;
i:= 0;
while i<mdo
r:= r∗n;
i:= i+ 1
sẽ là
A(m≥0) ∧(n≥0).
B(m≥0) ∧(n > 0).
Cm > 0.
D(m > 0) ∧(n > 0).
Câu 18. Liệu có thể sử dụng một automata hữu hạn đơn định và tối giản để mô tả hệ thống hiển thị
thông tin (mức nhiên liệu, tốc độ di chuyển, vị trí GPS, ngày, giờ) trên mặt biển báo của một
loại phương tiện cơ giới đặc thù chỉ với một nút nhấn không?
AKhông thể.
BCó thể sử dụng một DFA tối giản mà số lượng trạng thái vô hạn.
CCó thể sử dụng một DFA tối giản gồm ba trạng thái.
DCó thể sử dụng một DFA tối giản có hơn ba trạng thái.
Câu 19. Xét Σ = {a, b, c}và L={ab, ca, a, bb, bc}. Chuỗi nào dưới đây thuộc vào L∗.
Aabaacbb
Bbbabacabbbaaa
Cabcabbbbba
Daabbbcabbba
Câu 20. Biểu thức nào sau đây là biểu thức chính quy biểu diễn tập các chuỗi trên Σ = {a, b}có chứa
chuỗi con ab và chuỗi con ba?
A(a+b+a(a∪b)∗)·(b+a+b(a∪b)∗).
B(a∗b∗a(a∪b)+)∪(b∗a∗b(a∪b)+).
C(a∗b∗a(a∪b)+)·(b∗a∗b(a∪b)+).
D(a+b+a(a∪b)∗)∪(b+a+b(a∪b)∗).
Câu 21. Đáp án nào là phản ví dụ cho thấy hai automata bên dưới không tương đương?
q0
q1q2
q3
b
a
a
a
a
b
a
b
p0
p1p2
p3
bb
a
a
b
aa
a
Aabaab
Bbaab
Cbabb
Dabbaa
Câu 22. Phát biểu nào sau đây đúng cho tính đúng đắn (correctness) đối với các bộ ba Hoare, trong đó
downfac là chương trình như trong Câu 12?
A|=par (|>|)if (b > 0) {c=a+b}else c=a−b(|ψ|),và |=tot (|>|)downfac (|y=x!|).
B|=tot (|>|)if (b > 0) {c=a+b}else c=a−b(|ψ|),và |=par (|>|)downfac (|y=x!|).
C|=par (|>|)if (b > 0) {c=a+b}else c=a−b(|ψ|),và |=par (|>|)downfac (|y=x!|).
D|=tot (|>|)if (b > 0) {c=a+b}else c=a−b(|ψ|),và |=tot (|>|)downfac (|y=x!|).
Câu 23. Hai biểu thức chính qui: E1= ((c+b)∗(a+c))∗và E2= (ba +bc +ca +c)∗có biểu diễn cùng
một ngôn ngữ không?
ABiểu diễn cùng ngôn ngữ
BKhông tương đương
CE2⊇E1
DE1⊆E2
Chữ ký SV:.................. Mã đề 1913 (B01) Trang 4
Câu 24. Xét Σ = {a, b, c}và L={a, ab, bc, ba}. Chuỗi nào dưới đây không thuộc vào L5.
Aaabcabba
Bbcbaaaa
Caaaaa
Dabaababca
Câu 25. Cách nào dưới đây có thể xác định hai automata hữu hạn (FA) là tương đương?
ASo sánh số trạng thái của hai FA.
BChuyển về các biểu thức chính quy tương đương để chứng minh bằng toán học.
CChuyền về so sánh bảng chuyển trạng thái của hai automata tối ưu tương ứng.
DÁp dụng vét cạn các trường hợp dựa trên bảng chuyển trạng thái.
Câu 26. Xét đoạn chương trình sau.
Dạng bất biến (invariant form) nên được sử dụng để chứng minh tính đúng đắn của nó là
A{(s=Pi
k=1 b[k]) ∧2020 >i>0}.
B{(s=P2020
k=1 b[k]) ∧2020 > i ≥0}.
C{(s=Pi−1
k=0 b[k]) ∧2020 ≥i≥0}.
D{(s=Pi−1
k=1 b[k]) ∧2020 ≥i > 0}.
Câu 27. Dạng bất biến (invariant form) của chương trình While như trong Câu 17 mà có thể dùng trong
việc chứng minh tính đúng đắn của nó là sẽ là
A(r=ni)∧(0 ≤i≤m).
B(r=ni)∧(0 ≤i≤m)∧(n > 0).
C(r=ni)∧(0 ≤i≤m)∧(n≥0).
D(r=ni)∧(n > 0).
Câu 28. Luật đúng đắn bộ phận (partial correctness) cho cấu trúc while được phát biểu như sau
A(|φ∧B|)C(|ψ|)
(|φ|)while B{C}(|ψ∧ ¬B|).
B(|ψ∧B|)C(|ψ|)
(|ψ|)while B{C}(|ψ∧ ¬B|).
C(|φ∧B|)C(|ψ|)
(|φ|)while B{C}(|ψ|).
D(|ψ∧B|)C(|ψ|)
(|ψ|)while B{C}(|ψ|).
Câu 29. Xét đoạn chương trình sau.
Dạng bất biến (invariant form) nên được sử dụng để chứng minh tính đúng đắn của nó với tiền
điều kiện {y=y0∧y≥0}là
A{z=x(y0−y)∧y > 0}.
B{z=x(y−y0)∧y0≥0}.
C{z=x(y0−y)∧y≥0}.
D{z=x(y−y0)∧y0>0}.
Chữ ký SV:.................. Mã đề 1913 (B01) Trang 5