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

Bài giảng Ngôn ngữ hình thức: Chương 4 - Nguyễn Thị Hồng

Chia sẻ: _ _ | Ngày: | Loại File: PPT | Số trang:29

Báo xấu

19
lượt xem 3
download

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

Bài giảng Ngôn ngữ hình thức: Chương 4 Ôtômat đẩy xuống, cung cấp cho người học những kiến thức như: Ô tô mát đẩy xuống; Sự tương đương giữa các loại ô tô mát đẩy xuống; Mối quan hệ giữa ô tô mát đẩy xuống và văn phạm phi ngữ cảnh; Ngôn ngữ phi ngữ cảnh. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Ngôn ngữ hình thức: Chương 4 - Nguyễn Thị Hồng

Chương 4 Ôtômat đẩy xuống GV: Nguyễn Thi Hô ̣ ̀ng Email: nguyenhong@hnue.edu.vn
Nội dung  Ô tô mát đẩy xuống  Sự tương đương giữa các loại ô tô mát đẩy xuống  Mối quan hệ giữa ô tô mát đẩy xuống và văn phạm phi ngữ cảnh  Ngôn ngữ phi ngữ cảnh
Ô tô mát đẩy xuống (ODX)  Mô tả trực quan:
Ô tô mát đẩy xuống  Cấu tạo:  Một băng vào chứa các kí hiệu của xâu vào  Một đầu đọc duyệt băng từ trái qua phải  Một bộ điều khiển các trạng thái hữu hạn  Một stack có khả năng nhớ vô hạn, lúc đầu là rỗng (lúc đầu stack chứa một kí hiệu đặc biệt để đánh dấu đáy stack)
Hoạt động của Ô tô mát đẩy xuống  Ban đầu, stack là rỗng  Quá trình thực hiện của ô tô mát đẩy xuống tương tự như ô tô mát hữu hạn không tiền định  Mỗi bước thực hiện của Ô tô mát đẩy xuống căn cứ vào ba yếu tố:  Kí hiệu ở đỉnh stack  Trạng thái của ô tô mát  Kí hiệu đọc được trên băng vào
Hoạt động của Ô tô mát đẩy xuống  Mỗi dịch chuyển gồm các hành động:  Thay đổi nội dung stack (đỉnh stack)  Thay đổi trạng thái  Đầu đọc dịch sang phải một ô  Chú ý: tồn tại dịch chuyển nghĩa là kí hiệu trên băng không được tham khảo (đầu đọc không dịch chuyển sang phải)
Sự đoán nhận của ODX  Có hai cách thừa nhận xâu:  Xâu vào được thừa nhận khi ô tô mát đọc hết xâu và đến một trạng thái thừa nhận  Xâu vào được thừa nhận khi ô tô mát đọc hết xâu và lúc đó stack rỗng.
Ô tô mát đẩy xuống  Định nghĩa IV.1 Ô tô mát đẩy xuống không tiền định là một bộ 7 thành phần: M (Σ, Q, Γ, δ, q0, Z0, F)  Q : tập hữu hạn các trạng thái  Σ : bộ chữ vào  Γ : bộ chữ cái Stack, Q Γ= Ø  δ : hàm chuyển Γ x Q x (Σ {ε}) → tập con của Q x Γ*  q0 : trạng thái khởi đầu  Z0 : ký hiệu bắt đầu trên Stack(đáy stack)  F Q : tập các trạng thái kết thúc
Ô tô mát đẩy xuống  Ta gọi hình trạng của ô tô mát đẩy xuống là mọi xâu có dạng qw trong đó Γ*, q Q, w *  Hình trạng có dạng Z0q0x được gọi là hình trạng ban đầu  Hệ viết lại ngầm định trong M là W=(V, P):  V=Q Γ  P: ( ,p) δ(z,q,a) hay zqa p là một quy tắc trong P
Ô tô mát đẩy xuống  Ngôn ngữ được thừa nhận theo trạng thái cuối bởi ODX M là: L(M)={w *| Z0q0w=>*M p, Γ*, p F}  Ngôn ngữ được thừa nhận theo stack rỗng bởi ODX M là: N(M)={w *| Z0q0w=>*M p, p Q}
Ví dụ về ô tô mát đẩy xuống  Ví dụ 1: Ngôn ngữ L={anbn|n≥0} được đoán nhận theo trạng thái cuối của ODX M:  M=({a,b}, {q ,q ,q },{Z,a}, , q , Z, {q }) 0 1 2 0 0  Với : (Z,q ,a)={(Za,q )} nạp a và stack 0 1 (a,q1,a)={(aa,q1)} nạp tiếp a vào stack (a,q1,b)={( ,q2)} xóa a khỏi stack (a,q2,b)={( ,q2)} tiếp tục xóa a khỏi stack (Z,q2, )={( ,q0)} về trạng thái thừa nhận Quá trình dịch chuyển của M với xâu aabb Zq0aabb=>Zaq1abb=>Zaaq1bb=>Zaq2b=>Zq2=>q0 Vì q0 F nên aabb L(M)
Ví dụ về ô tô mát đẩy xuống  Ví dụ 2: Ngôn ngữ L={wwR|w {a,b}*} được thừa nhận theo stack rỗng bởi ODX M:  M=({a,b}, {q ,q },{Z,a,b}, , q , Z, ) 0 1 0  Với : (Z,q0,a)={(Za,q0)} (Z,q0,b)={(Zb,q0)} (a,q0,b)={(ab,q0)} (b,q0,a)={(ba,q0)} (b,q0,b)={(bb,q0),( ,q1)} (a,q0,a)={(aa,q0),( ,q1)} (a,q1,a)={( ,q1)} (b,q1,b)={( ,q1)} (Z,q1, )={( ,q1)} (Z,q0, )={( ,q0)}
Ví dụ 2  Cây hình trạng với xâu vào là abba:  Xâu abba là thuộc ngôn ngữ N(M) vì có một đường (một suy dẫn) hình trạng Zq0abba đến hình trạng q1(stack rỗng)
Các tính chất cơ bản của ODX  Cho M (Σ, Q, Γ, δ, q0, Z0, F) là ô tô mát đẩy xuống có các quy tắc trong hệ viết lại: Zpa q (trong đó p, q Q, Z Γ, a Σ*, Γ*, |Z|=1, |a|≤1, | |≥0):  Nếu |a|=1 thì độ dài phần xâu chưa được đọc sẽ giảm 1.  Nếu | |=0 thì độ dài stack giảm 1.
Sự tương đương giữa các ODX  Định lý IV.4: Cho L=L(M) trong đó M là một ODX. Tồn tại một ODX M’ sao cho L=N(M’) ( Nghĩa là Nếu L được đoán nhận bởi ODX theo kiểu trạng thái cuối thì L cũng được đoán nhận bởi một ODX theo kiểu stack rỗng).
Sự tương đương giữa các ODX  Giả sử M=( , Q, , , q0, Z0, F)  Xây dựng ô tô mát M’:  Thêm hai trạng thái mới q ’ và q và một kí hiệu đáy stack 0 e mới X0: M’=( , Q {q0’, qe}, {X0}, ’, q0’, X0, )  Hàm dịch chuyển ’ được xác định như sau: (1) ’(X0, q0’, ) = {(X0Z0, q0)} (2) ’(Z, q, a) = (Z, q, a) (với mọi q Q\F, a { }, Z ) (3) ’(Z, q, a) = (Z, q, a), ’(Z, q, ) = (Z, q, ) {( , qe)} (với mọi q F, a và Z ) (4) ’(X0, q, ) ={( , qe)} (với mọi q F)
Sự tương đương giữa các ODX  Ví dụ: Ngôn ngữ L={anbn|n≥0} được đoán nhận theo trạng thái cuối của ODX M:  M=({a,b}, {q ,q ,q },{Z,a}, , q , Z, {q }) 0 1 2 0 0  Với : (Z,q ,a)={(Za,q )} nạp a và stack 0 1 (a,q1,a)={(aa,q1)} nạp tiếp a vào stack (a,q1,b)={( ,q2)} xóa a khỏi stack (a,q2,b)={( ,q2)} tiếp tục xóa a khỏi stack (Z,q2, )={( ,q0)} về trạng thái thừa nhận M đoán nhận ngôn ngữ trên theo trạng thái cuối.  Xây dựng M’ cũng đoán nhận ngôn ngữ trên theo stack rỗng
Sự tương đương giữa các ODX  Xây dựng M’=({a,b}, {q0,q1,q2,q0’,qe},{Z,a,X}, ’, q0’, X, ) trong đó ’ gồm các sản xuất sau:  Quy tắc (1): ’(X,q ’, )={XZ,q } 0 0  Quy tắc (2): ’(a,q ,a)={aa,q }, ’(a,q ,b)={( ,q )}, 1 1 1 2 ’(a,q2,b)={( ,q2)}, ’(Z,q2, )={( ,q0)}  Quy tắc (3): ’(Z,q ,a)={(Za,q )}, ’(Z,q , )={( ,q )}, 0 1 0 e ’(a,q0, )={( ,qe)}  Quy tắc (4): ’(X,q , )={( ,q )} 0 e  Quy tắc (5): ’(Z,q , )={( ,q )}, ’(a,q , )={( ,q )}, e e e e ’(X,qe, )={( ,qe)}  Một suy dẫn
Sự tương đương giữa các ODX  Với xâu đầu vào aabb, chuỗi suy dẫn như sau:  Như vậy quá trình suy dẫn kết thúc khi đọc hết xâu, trạng thái là qe và stack rỗng => xâu aabb được ô tô mát thừa nhận theo hình thức stack rỗng.
Sự tương đương giữa các ODX  Định lý IV.5: Cho L=N(M) trong đó M là một ODX. Tồn tại một ODX M’ sao cho L=L(M’) Chứng minh:  Giả sử M=( , Q, , , q , Z , ) 0 0  Xây dựng ô tô mát M’: thêm hai trạng thái mới q0’ và qf , và một kí hiệu đáy stack mới X0: M’=( , Q {q0’, qf}, {X0}, ’, q0’, X0, {qf})

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.