zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Automata

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

Báo xấu

165
lượt xem 26
download

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Automata

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 >
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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.