Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 | TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT TRUYỀN THÔNG Đề thi môn TIN HỌC LÝ THUYẾT 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 diem Á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 a bJ cJ 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 start a b a a b Câu 3 1.5 diem 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 diem 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.Ớ đ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 diem 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ữ chính quy L a bJ cJ 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ó uv w e 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 . 2 2 ni11in i Ầ-i Xét chuỗi uv w ta thấy chuỗi uv w so với chuỗi uvw z abcd 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 .
