Đề thi môn tin học lý thuyết

Chia sẻ: Chao Hello | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

470
lượt xem 81
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Câu 1 (1.0 điểm): Áp dụng bổ đề bơm, bạn hãy chứng minh ngôn ngữ sau đây không là ngôn ngữ chính quy: L = {ai bj cj di | i, j ≥ 1} Câu 2 (2.0 điểm): Bạn hãy tìm một DFA tương đương với NFA sau: Câu 3 (1.5 điểm): Bạn hãy vẽ một automata hữu hạn chấp nhận cho ngôn ngữ được ký hiệu bởi biểu thức chính quy sau: ( (a + ab) b* a )* Câu 4 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Chomsky (cho biết rằng văn phạm không có ký hiệu vô ích): S...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi môn tin học lý thuyết

TRƯỜNG ĐẠI HỌC CẦN THƠ Đề thi môn: TIN HỌC LÝ THUYẾT KHOA CNTT & TRUYỀN THÔNG Lớp: TIN HỌC K.29 Lần 2 – Học kỳ 1 – Năm học 06 - 07 Thời gian làm bài: 120 phút NỘI DUNG ĐỀ Câu 1 (1.0 điểm): Áp dụng bổ đề bơm, bạn hãy chứng minh ngôn ngữ sau đây không là ngôn ngữ ijji chính quy: L = {a b c d | i, j ≥ 1} Câu 2 (2.0 điểm): Bạn hãy tìm một DFA tương đương với NFA sau: b a a, b a, b start q1 q2 q3 Câu 3 (1.5 điểm): Bạn hãy vẽ một automata hữu hạn chấp nhận cho ngôn ngữ được ký hiệu bởi biểu thức chính quy sau: ( (a + ab) b* a )* Câu 4 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Chomsky (cho biết rằng văn phạm không có ký hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1 Câu 5 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Greibach: S → SA | 0 A → AS | 1 Câu 6 (1.5 điểm): Bạn hãy thiết kế một PDA tương đương với văn phạm phi ngữ cảnh có tập luật sinh như sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1 Câu 7 (2.0 điểm): Bạn hãy thiết kế một máy Turing để thực hiện phép nhân 3 một số nguyên n dương (n > 0). Chú ý: trên băng nhập đã được cho trước một ký hiệu X ở đầu băng. Đầu đọc đang chỉ tại vị trí đầu tiên của băng nhập (ký hiệu X). Ví dụ: thực hiện phép nhân 3 cho số n = 3 (3 * 3 = 9) Đầu vào (input): X000 Kết quả (output): 000000000 (9 số 0) - HẾT - ĐHCT, ngày 02 tháng 02 năm 2007 Giáo viên ra đề Nguyễn Thanh Bình
ĐÁP ÁN Câu 1 (1.0 điểm): Áp dụng bổ đề bơm, bạn hãy chứng minh ngôn ngữ sau đây không là ngôn ngữ ijji chính quy: L = {a b c d | i, j ≥ 1} Giả sử L là ngôn ngữ chính quy. Khi đó sẽ tồn tại một DFA M chấp nhận cho ngôn ngữ L. Gọi n là số trạng thái của DFA M đó. Xét chuỗi z = anb1c1dn . Ta có độ dài của chuỗi z là: |z| = 2n + 2 > n . Theo bổ đề bơm, ta có thể đặt z = uvw , trong đó u, v, w là các chuỗi con của z với điều kiện như sau: |uv| ≤ n, |v| ≥ 1 và với mọi i ≥ 0 ta có uviw ϵ L Do uv là chuỗi tiền tố của chuỗi z = anb1c1dn và uv có độ dài chuỗi không lớn hơn n nên uv chỉ chứa ký tự a. Vậy v cũng chỉ chứa ký hiệu a (và có ít nhất một ký hiệu a). Xét chuỗi uv2w, ta thấy chuỗi uv2w so với chuỗi uvw = z = anb1c1dn có nhiều hơn một chuỗi v. Mặt khác, trong chuỗi v chỉ chứa ký hiệu a, nên ta suy ra trong chuỗi uv2w sẽ có số ký hiệu a lớn hơn n (và số ký hiệu d không đổi là n). Vậy trong chuỗi uv2w sẽ có số ký hiệu a nhiều hơn ký hiệu d, hay chuỗi uv2w không thuộc ngôn ngữ L. Vậy giả thiết L là ngôn ngữ chính quy sai, hay L không là ngôn ngữ chính quy. Câu 2 (2.0 điểm): Bạn hãy tìm một DFA tương đương với NFA sau: b a a, b a, b start q1 q2 q3 DFA tương đương: b start b b [q 1] [q 1, q 2] [q 1,q 2,q 3] a a a a a [q 2] [q 2, q 3] b b [q 3] Câu 3 (1.5 điểm): Bạn hãy vẽ một automata hữu hạn chấp nhận cho ngôn ngữ được ký hiệu bởi biểu thức chính quy sau: ( (a + ab) b* a )* b Cách 1: a start q2 q1 a a b q3
Cách 2: sử dụng cách vẽ đã học theo định lý 3.3 – Giáo trình Tin học lý thuyết – MSc. Võ Huỳnh Trâm – Đại học Cần Thơ – 2003. Câu 4 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Chomsky (cho biết rằng văn phạm không có ký hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1 Bước 1: bỏ qua (vì đề bài đã cho biết văn phạm không có ký hiệu vô ích, và nhìn vào văn phạm ta thấy không có luật sinh ε hay luật sinh đơn vị). Bước 2: thay thế các ký hiệu kết thúc ở các luật sinh có độ dài vế phải lớn hơn 1 bằng các biến tương ứng. S → C0SA | C1SB | C0C1 A → C0A | 0 B → C1B | 1 C0 → 0 C1 → 1 Bước 3: thay thế luật sinh có độ dài vế phải lớn hơn 2 bằng các luật sinh có độ dài vế phải bằng 2. S → C0D0 | C1D1 | C0C1 A → C0A | 0 B → C1B | 1 C0 → 0 C1 → 1 D0 → SA D1 → SB Câu 5 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Greibach: S → SA | 0 A → AS | 1 Bước 1: văn phạm đã ở dạng chuẩn Chomsky. Bước 2: thay biến S bằng biến A1, biến A bằng biến A2. Ta có tập luật sinh: A1 → A1A2 | 0 A2 → A2A1 | 1 Bước 3: khử tính đệ quy trái ở tập luật sinh trên: A1 → 0 | 0B1 A2 → 1 | 1B2 B1 → A2 | A2B1 B2 → A1 | A1B2 Bước 4: các luật sinh từ biến A1 và A2 đã thỏa dạng chuẩn Greibach.
Bước 5: chuyển các luật sinh từ biến B1 và B2 về dạng chuẩn Greibach. A1 → 0 | 0B1 A2 → 1 | 1B2 B1 → 1 | 1B2 | 1B1 | 1B2B1 B2 → 0 | 0B1 | 0B2 | 0B1B2 Tập luật sinh trên đã thỏa dạng chuẩn Greibach. Câu 6 (1.5 điểm): Bạn hãy thiết kế một PDA tương đương với văn phạm phi ngữ cảnh có tập luật sinh như sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1 Xây dựng PDA M như sau: M ({q}, {0, 1}, {S, A, B}, δ, q, S, Ø) Với các hàm chuyển δ như sau: δ (q, 0, S) = { (q, SA), (q, ε) } δ (q, 1, S) = { (q, SB), (q, ε) } δ (q, 0, A) = { (q, A), (q, ε) } δ (q, 1, B) = { (q, B), (q, ε) } Câu 7 (2.0 điểm): Bạn hãy thiết kế một máy Turing để thực hiện phép nhân 3 một số nguyên n dương (n > 0). Chú ý: trên băng nhập đã được cho trước một ký hiệu X ở đầu băng. Đầu đọc đang chỉ tại vị trí đầu tiên của băng nhập (ký hiệu X). Ý tưởng: a) Đổi X thành B (để làm chốt chặn ở đầu chuỗi) b) Gặp số 0 đầu tiên đổi thành 1 (đổi thành 1 để đánh dấu số 0 đó đã được xét) c) Di chuyển đến cuối chuỗi, đổi 2 ký hiệu B thành ký hiệu 2. d) Di chuyển về đầu chuỗi cho đến khi gặp ký hiệu 1, dịch phải. 1. Nếu ký hiệu tiếp theo là 0, lặp lại bước b. 2. Nếu ký hiệu tiếp theo là 2 thì di chuyển về cuối chuỗi (cho đến khi gặp B), sau đó dịch trái đổi các ký hiệu 1 và 2 thành 0. Gặp ký hiệu B ở đầu chuỗi thì kết thúc. (0, 0, R) (0, 0, L) (2, 2, R) (2, 2, L) start (X, B, R) (0, 1, R) (B, 2, R) (B, 2, L) q0 q1 q2 q3 q4 (1, 1, R) (2, 2, R) (2, 0, L) (1, 0, L) (2, 2, R) (B, B, L) q5 q6 q7 (B, B, Ø) -- HẾT --