Câu 1 ( đ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 ( điểm): Bạn hãy tìm một DFA tương đương với NFA sau: Câu 3 ( đ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 ( đ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. | 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 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 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 diem 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 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 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 diem 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 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 diem 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 ở dầ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 đ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 .
