Đề thi môn ngôn ngữ hình thức và otomat

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
Nội dung trích xuất từ tài liệu:
Đề thi môn ngôn ngữ hình thức và otomat 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ữ i j j i 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 start a, b a, b 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ữ i j j i 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 start a, b a, b 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 )* Cách 1: b a start q1 q2 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 t ...