Xem mẫu
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN TOÁN TIN ỨNG DỤNG
KIỂM TRA GIỮA KỲ - NĂM HỌC 2014-2015
MÔN HỌC OTOMAT&NNHT- Đề A153
(Thời gian làm bài 45 phút)
Đáp án & Thang điểm: Có 10 ý nhỏ, mỗi ý cho 1 điểm, có thể chấp nhận sai sót nhỏ, hoặc nhầm lẫn
(mà không phải là chép!)
Câu 1. (3 điểm). Cho văn phạm G = , với P = {SaS1, S1aS1 | bS1 | a}.
a/. Gọi L = L(G), L là ngôn ngữ chính quy hay phi ngữ cảnh?. Viết 5 từ đầu tiên của ngôn ngữ
L (xếp theo độ dài tăng dần và theo thứ tự từ điển).
Giải: Do G là Văn phạm CQ nên L là ngôn ngữ CQ (0.5);
L = {aa, aaa, aba, aaaa, aaba …}(0.5), nếu viết đúng thứ tự < 4 từ : không cho điểm, đúng 4-5
từ cho đủ điểm)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải: Viết được L = {a a | {a, b}*}, hoặc mô tả được L là ngôn ngữ gồm các từ trên
bảng chữ cái {a, b}, được bắt đầu và kết thúc bởi ký hiệu ‘a’. (đều cho 1.0)
c/. Xây dựng otomat hữu hạn A sao cho T(A) = L(G).
Giải: Từ văn phạm G, xây dựng otomat A như sau: A = < { S, S 1 , E}, {a, b}, , S, {E} >,
trong đó hàm xác định như sau: (S, b) = ; (S, a) = S1 ; (S1, a) = {S1, E}, (S1, b) = S1,
(E, a) = (E, b) = . (1.0)
Có thể chỉ cần cho A bằng đồ thị chuyển trạng thái (hoặc bảng chuyển trạng thái): (1.0)
Câu 2. (4 điểm). Cho otomat hữu hạn A có đồ thị chuyển như hình vẽ:
a/. A là otomat loại gì ? (DFA, NFA, đầy đủ hay không đầy đủ)
Giải: Suy luận trực tiếp từ các cung trên đồ thị, hoặc
đưa về dạng bảng, rồi kết luận là DFA và đầy đủ (1.0).
(nếu chỉ kết luận không giải thích cho 0.5)
b/. Xác định ngôn ngữ L = T(A).
Giải: L = { 1n0m 1 | n > 0, m > 1, {0, 1}* }. (1.0)
c/. Xây dựng văn phạm G sao cho L(G) = T(A).
Giải: G = < {0, 1}; {q0, q1, q2}, q0, { q01q0 | 0q1 ; q10q1 |1q2 |1; q20q2 |1q2| 0 |1}>
(nếu thiếu 1 vài quy tắc vẫn cho đủ 1.0 điểm)
d/. L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: L là ngôn ngữ chính quy vì được đoán nhận bởi otomat hữu hạn. (hoặc do L đươc sinh
bởi Văn phạm CQ lập ở phàn c/. (1.0)
Câu 3 . (3 điểm). Cho ngôn ngữ L = {a}+.{b}* .
a/. Viết 7 từ đầu tiên của ngôn ngữ L (xếp theo độ dài tăng dần và theo thứ tự từ điển). L là
ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: - L = {a, aa, ab, aab, abb…} (sai 1 từ vấn cho đủ 0.5)
- Do {a}+ và {b}* là các ngôn ngữ CQ, L là tích ghép của 2 ngôn ngữ CQ nên cũng
là chính quy. (hoặc nhận xét khác đúng đều cho 0.5)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải : L = {anbm | m > 0, n > 1} (1.0)
c/. Viết biểu thức chính quy biểu diễn ngôn ngữ L.
Giải : r = a+ .b* (1.0)
Tổng cộng 10 điểm
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN TOÁN TIN ỨNG DỤNG
KIỂM TRA GIỮA KỲ - NĂM HỌC 2014-2015
MÔN HỌC OTOMAT&NNHT- Đề A154
(Thời gian làm bài 45 phút)
Đáp án & Thang điểm: Có 10 ý nhỏ, mỗi ý cho 1 điểm, có thể chấp nhận sai sót nhỏ, hoặc nhầm lẫn
(mà không phải là chép!)
Câu 1. (3 điểm). Cho văn phạm G = , với P = {SbS1, S1aS1 | bS1 | b }.
a/. Gọi L = L(G), L là ngôn ngữ chính quy hay phi ngữ cảnh?. Xâu = babab có thuộc ngôn
ngữ L(G) hay không, nếu có hãy viết dãy suy dẫn đầy đủ của từ = babab trong văn phạm G.
Giải: Do G là Văn phạm CQ nên L là ngôn ngữ CQ (0.5);
dãy suy dẫn đầy đủ của từ : S ├ bS1├ baS1├ babS1├ babaS1├ babab (0.5)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải: Viết được L = {b b | {a, b}*}, hoặc mô tả được L là ngôn ngữ gồm các từ trên
bảng chữ cái {a, b}, được bắt đầu và kết thúc bởi ký hiệu ‘b’. (đều cho 1.0)
c/. Xây dựng otomat hữu hạn A sao cho T(A) = L(G).
Giải: Từ văn phạm G, xây dựng otomat A như sau: A = < { S, S1 , E}, {a, b}, , S, {E} >,
trong đó hàm xác định như sau: (S, a) = ; (S, b) = S1 ; (S1, a) = S1 ; (S1, b) = {S1, E},
(E, a) = (E, b) = . (1.0)
Có thể chỉ cần cho A bằng đồ thị chuyển trạng thái (hoặc bảng chuyển trạng thái): (1.0)
Câu 2. (4 điểm). Cho otomat hữu hạn A có đồ thị chuyển như hình vẽ:
a/. A là otomat loại gì ? (DFA, NFA, đầy đủ hay không đầy đủ)
Giải: Suy luận trực tiếp từ các cung trên đồ thị, hoặc
đưa về dạng bảng, rồi kết luận là DFA và không đầy đủ
(nếu chỉ kết luận đúng không giải thích cho 0.5)
b/. Xác định ngôn ngữ L = T(A).
Giải: L = { 1n01m 0 | n, m > 0, m > 1 }. (1.0)
c/. Xây dựng văn phạm G sao cho L(G) = T(A).
Giải: G = < {0, 1}; {q0, q1, q2}, q0, { q01q0 | 0q1 ; q11q1 | 0q2 | 0}>
(nếu thiếu 1 vài quy tắc vẫn cho đủ 1.0 điểm)
d/. L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: L là ngôn ngữ chính quy vì được đớn nhận bởi otomat hữu hạn (1.0) (hoặc được sinh bởi
văn phạm chính quy vừa xây dựng, cũng cho 1.0))
Câu 3 . (3 điểm). Cho ngôn ngữ L = {a}*.{b}+ .
a/. Viết 7 từ đầu tiên của ngôn ngữ L (xếp theo độ dài tăng dần và theo thứ tự từ điển). L là
ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: - L = {b, ab, bb, aab, abb, bbb, aaab…} (sai 1-2 từ vấn cho đủ 0.5)
- Do {a}* và {b}+ là các ngôn ngữ CQ, L là tích ghép của 2 ngôn ngữ CQ nên cũng
là chính quy. (hoặc nhận xét khác đúng đều cho 0.5)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải : L = {anbm | n > 0, m > 1} (1.0)
c/. Viết biểu thức chính quy biểu diễn ngôn ngữ L.
Giải : r = a* .b+ (1.0)
Tổng cộng 10 điểm
nguon tai.lieu . vn
BỘ MÔN TOÁN TIN ỨNG DỤNG
KIỂM TRA GIỮA KỲ - NĂM HỌC 2014-2015
MÔN HỌC OTOMAT&NNHT- Đề A153
(Thời gian làm bài 45 phút)
Đáp án & Thang điểm: Có 10 ý nhỏ, mỗi ý cho 1 điểm, có thể chấp nhận sai sót nhỏ, hoặc nhầm lẫn
(mà không phải là chép!)
Câu 1. (3 điểm). Cho văn phạm G = , với P = {SaS1, S1aS1 | bS1 | a}.
a/. Gọi L = L(G), L là ngôn ngữ chính quy hay phi ngữ cảnh?. Viết 5 từ đầu tiên của ngôn ngữ
L (xếp theo độ dài tăng dần và theo thứ tự từ điển).
Giải: Do G là Văn phạm CQ nên L là ngôn ngữ CQ (0.5);
L = {aa, aaa, aba, aaaa, aaba …}(0.5), nếu viết đúng thứ tự < 4 từ : không cho điểm, đúng 4-5
từ cho đủ điểm)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải: Viết được L = {a a | {a, b}*}, hoặc mô tả được L là ngôn ngữ gồm các từ trên
bảng chữ cái {a, b}, được bắt đầu và kết thúc bởi ký hiệu ‘a’. (đều cho 1.0)
c/. Xây dựng otomat hữu hạn A sao cho T(A) = L(G).
Giải: Từ văn phạm G, xây dựng otomat A như sau: A = < { S, S 1 , E}, {a, b}, , S, {E} >,
trong đó hàm xác định như sau: (S, b) = ; (S, a) = S1 ; (S1, a) = {S1, E}, (S1, b) = S1,
(E, a) = (E, b) = . (1.0)
Có thể chỉ cần cho A bằng đồ thị chuyển trạng thái (hoặc bảng chuyển trạng thái): (1.0)
Câu 2. (4 điểm). Cho otomat hữu hạn A có đồ thị chuyển như hình vẽ:
a/. A là otomat loại gì ? (DFA, NFA, đầy đủ hay không đầy đủ)
Giải: Suy luận trực tiếp từ các cung trên đồ thị, hoặc
đưa về dạng bảng, rồi kết luận là DFA và đầy đủ (1.0).
(nếu chỉ kết luận không giải thích cho 0.5)
b/. Xác định ngôn ngữ L = T(A).
Giải: L = { 1n0m 1 | n > 0, m > 1, {0, 1}* }. (1.0)
c/. Xây dựng văn phạm G sao cho L(G) = T(A).
Giải: G = < {0, 1}; {q0, q1, q2}, q0, { q01q0 | 0q1 ; q10q1 |1q2 |1; q20q2 |1q2| 0 |1}>
(nếu thiếu 1 vài quy tắc vẫn cho đủ 1.0 điểm)
d/. L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: L là ngôn ngữ chính quy vì được đoán nhận bởi otomat hữu hạn. (hoặc do L đươc sinh
bởi Văn phạm CQ lập ở phàn c/. (1.0)
Câu 3 . (3 điểm). Cho ngôn ngữ L = {a}+.{b}* .
a/. Viết 7 từ đầu tiên của ngôn ngữ L (xếp theo độ dài tăng dần và theo thứ tự từ điển). L là
ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: - L = {a, aa, ab, aab, abb…} (sai 1 từ vấn cho đủ 0.5)
- Do {a}+ và {b}* là các ngôn ngữ CQ, L là tích ghép của 2 ngôn ngữ CQ nên cũng
là chính quy. (hoặc nhận xét khác đúng đều cho 0.5)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải : L = {anbm | m > 0, n > 1} (1.0)
c/. Viết biểu thức chính quy biểu diễn ngôn ngữ L.
Giải : r = a+ .b* (1.0)
Tổng cộng 10 điểm
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN TOÁN TIN ỨNG DỤNG
KIỂM TRA GIỮA KỲ - NĂM HỌC 2014-2015
MÔN HỌC OTOMAT&NNHT- Đề A154
(Thời gian làm bài 45 phút)
Đáp án & Thang điểm: Có 10 ý nhỏ, mỗi ý cho 1 điểm, có thể chấp nhận sai sót nhỏ, hoặc nhầm lẫn
(mà không phải là chép!)
Câu 1. (3 điểm). Cho văn phạm G = , với P = {SbS1, S1aS1 | bS1 | b }.
a/. Gọi L = L(G), L là ngôn ngữ chính quy hay phi ngữ cảnh?. Xâu = babab có thuộc ngôn
ngữ L(G) hay không, nếu có hãy viết dãy suy dẫn đầy đủ của từ = babab trong văn phạm G.
Giải: Do G là Văn phạm CQ nên L là ngôn ngữ CQ (0.5);
dãy suy dẫn đầy đủ của từ : S ├ bS1├ baS1├ babS1├ babaS1├ babab (0.5)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải: Viết được L = {b b | {a, b}*}, hoặc mô tả được L là ngôn ngữ gồm các từ trên
bảng chữ cái {a, b}, được bắt đầu và kết thúc bởi ký hiệu ‘b’. (đều cho 1.0)
c/. Xây dựng otomat hữu hạn A sao cho T(A) = L(G).
Giải: Từ văn phạm G, xây dựng otomat A như sau: A = < { S, S1 , E}, {a, b}, , S, {E} >,
trong đó hàm xác định như sau: (S, a) = ; (S, b) = S1 ; (S1, a) = S1 ; (S1, b) = {S1, E},
(E, a) = (E, b) = . (1.0)
Có thể chỉ cần cho A bằng đồ thị chuyển trạng thái (hoặc bảng chuyển trạng thái): (1.0)
Câu 2. (4 điểm). Cho otomat hữu hạn A có đồ thị chuyển như hình vẽ:
a/. A là otomat loại gì ? (DFA, NFA, đầy đủ hay không đầy đủ)
Giải: Suy luận trực tiếp từ các cung trên đồ thị, hoặc
đưa về dạng bảng, rồi kết luận là DFA và không đầy đủ
(nếu chỉ kết luận đúng không giải thích cho 0.5)
b/. Xác định ngôn ngữ L = T(A).
Giải: L = { 1n01m 0 | n, m > 0, m > 1 }. (1.0)
c/. Xây dựng văn phạm G sao cho L(G) = T(A).
Giải: G = < {0, 1}; {q0, q1, q2}, q0, { q01q0 | 0q1 ; q11q1 | 0q2 | 0}>
(nếu thiếu 1 vài quy tắc vẫn cho đủ 1.0 điểm)
d/. L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: L là ngôn ngữ chính quy vì được đớn nhận bởi otomat hữu hạn (1.0) (hoặc được sinh bởi
văn phạm chính quy vừa xây dựng, cũng cho 1.0))
Câu 3 . (3 điểm). Cho ngôn ngữ L = {a}*.{b}+ .
a/. Viết 7 từ đầu tiên của ngôn ngữ L (xếp theo độ dài tăng dần và theo thứ tự từ điển). L là
ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?
Giải: - L = {b, ab, bb, aab, abb, bbb, aaab…} (sai 1-2 từ vấn cho đủ 0.5)
- Do {a}* và {b}+ là các ngôn ngữ CQ, L là tích ghép của 2 ngôn ngữ CQ nên cũng
là chính quy. (hoặc nhận xét khác đúng đều cho 0.5)
b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.
Giải : L = {anbm | n > 0, m > 1} (1.0)
c/. Viết biểu thức chính quy biểu diễn ngôn ngữ L.
Giải : r = a* .b+ (1.0)
Tổng cộng 10 điểm