Automata

Chia sẻ: Hồ Viết Dũng | Ngày: | Loại File: DOC | Số trang:2

0
119
lượt xem
24
download

Automata

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

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}

Chủ đề:
Lưu

Nội dung Text: Automata

  1. DHLTTB01 TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HCM 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= < {a,b} , {S} , P , S > 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 (2.5 đ): 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 (2.5 đ): Xây dựng một automat đẩy ngược ( pushdown automata) chấp nhận văn phạm sau đây: G= < {a,b} , {S} , P , S > Với P = { S  aSb, S  λ} ( với λ là ký hiệu ký tự rỗng ) ------- hết ------- GIẢI Câu 7 (2.5 đ): Automat hữu hạn M sao cho chấp nhận ngôn ngữ L={(anb2 : n ≥ 0} là: M = (Q, Σ , δ , q0 , F) a a,b b b a,b q0 q1 q2 q3 a 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 (2.5 đ): Cho văn phạm sau đây: G= < {a,b} , {S} , P , S >
  2. DHLTTB01 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 (2.5 đ ): 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 (2.5 đ): 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
Đồng bộ tài khoản