tailieunhanh - Automata

Xây dựng một automat đẩy ngược ( pushdown automata) chấp nhận ngôn ngữ sau đây: L = {wwR : w e { a,b}* } với wR là sự đảo ngược của dòng ký tự w và tập ký tự của ngôn ngữ là {a,b} | TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP KHOA CÔNG NGHỆ THÔNG TIN ------- oOo ------- ĐỀ THI MẪU NĂM 2007 (A) Chuyên ngành: KHOA HỌC MÁY TÍNH Môn Thi: Automata Thời gian làm bài: 90 phút Câu 7 (2,5 đ): Cho I={a,b}. Hãy xây dựng một automat hữu hạn M sao cho chấp nhận ngôn ngữ L={(anb2 : n ≥ 0} Câu 9 (2,5 đ): Cho văn phạm sau đây: G= Với P = { S aSb, S } ( với là ký hiệu ký tự rỗng ) a) Hãy cho biết dạng thức của những dòng ký tự thuộc ngôn ngữ L(G). (0,5 điểm) b) Văn phạm G thuộc loại văn phạm gì ? Câu 8 ( đ): Xây dựng một automat đẩy ngược ( pushdown automata) chấp nhận ngôn ngữ sau đây: L= { an bn+1: n ≥ 1} Câu 6 ( đ): Xây dựng một automat đẩy ngược ( pushdown automata) chấp nhận văn phạm sau đây: G= Với P = { S aSb, S } ( với là ký hiệu ký tự rỗng ) ------- hết ------- GIẢI Câu 7 ( đ): Automat hữu hạn M sao cho chấp nhận ngôn ngữ L={(anb2 : n ≥ 0} là: M = (Q, , , q0 , F) Với : Q = { q0 , q1 , q2 , q3 } ; = { a,b} ; F = { q2} ( q0, a) = q0 ( q0, b) = q1 ( q1, a) = q3 ( q1, b) = q2 ( q2, a) = q3 ( q2, b) = q3 ( q3, a) = q3 ( q3, b) = q3 Câu 9 ( đ): Cho văn phạm sau đây: G= Với P = { S aSb, S } ( với là ký hiệu ký tự rỗng ) a) Đặt w { a,b}* , lúc đó từ P ta có: S aSa aaSbb a3S b3 anS bn Thế S vào ta được dạng thức của dòng ký tự thuộc L(G) là anS bn : n ≥ 0 b) Văn phạm G thuộc loại văn phạm tuyến tính ( hoặc văn phạm phi ngữ cảnh) Câu 8 ( đ ): Automat đẩy ngược ( pushdown automaton) chấp nhận ngôn ngữ L= { an bn+1: n ≥ 1} là: M = (Q, , , , q0 , z , F) Với : ( q0, a , z ) = {( q0 ,az)} , ( q0, a , a ) = {( q0 ,aa)} , ( q0, , a ) = {( q1 ,a)} , ( q1, b , a ) = {( q1 , )} , ( q1, b , z ) = {( q1 , )} , ( q1, , z ) = {( qf ,z)} , Q = { q0 , q1 , qf } ; = { a,b} ; = {a,z} ; F = { qf} Câu 10 ( đ): Xây dựng một automat đẩy ngược ( pushdown automata) chấp nhận ngôn ngữ sau đây: L = {wwR : w { a,b}* } với wR là sự đảo ngược của dòng ký tự w và tập ký tự của ngôn ngữ là {a,b} Giải : Automat đẩy ngược ( pushdown automata) chấp nhận ngôn ngữ L = {wwR : w { a,b}* } là: M = (Q, , , , q0 , z , F) Với : ( q0, a , z ) = {( q0 ,az)} , ( q0, a , a ) = {( q0 ,aa)} , ( q0, a , b ) = {( q0 ,ab)} , ( q0, b , a ) = {( q0 ,ba)} , ( q0, b , b ) = {( q0 ,bb)} , ( q0, b , z ) = {( q0 ,bz)} , ( q0, , a ) = {( q1 ,a)} , ( q0, , b ) = {( q1 ,b)} , ( q1, a , a ) = {( q1 , )}, ( q1, b , b ) = {( q1 , )}, ( q1, , z ) = {( qf ,z)} , Q = { q0 , q1 , qf } ; = { a,b} ; = {a,b,z} ; F = { qf} Ghi chú: . Ký tên: Trang: 2/2 DHLTTB01