khiem_duyenb4
New Member
Chia sẻ miễn phí cho các bạn tài liệu: Báo Cáo Bài Tập Lớn: Chuyển từ một NPDA sang một văn phạm phi ngữ cảnh
NHÓM 13-KHMT1-k2
March 23, 2010
BTL- Môn Automata
2
Chuyển từ một NPDA sang một
văn phạm phi ngữ cảnh.
I.Lý thuyết:
Bổ đề 7.1:
Với mọi npda luôn có một npda tương ứng thỏa mãn hai điều
kiệu sau:
1.Chỉ có 1 trạng thái kết thúc và npda kết thúc khi stack rỗng.2.Mọi chuyển trạng thái đều có dạng:
d(qi,a,A)={c1,c2,...,cn}
trong đó:
ci={qj,
l) (7.5)
hoặc:
ci=(qj,BC) (7.6)
tức là 1 di chuyển hoặc tăng hoặc giảm stack 1 ký hiệu đơn
Bây giờ ta sẽ đi vào chứng minh bổ đề
7.1
bằng cách xây dựng một NPDA
tương đương thỏa mãn 2 điều kiện trên.
-Điều kiện 1:
Giả sử một NPDA có nhiều hơn một trạng thái kết thúc qi,qj,qk.... Ta chuyển hết tất cả các trạng thái kết thúc qj,qk... về trạng thái kết thúc qi khi stack rỗng. Điều này tương đương với việc thêm các chuyển dịch delta như sau vào
d(qj, l,z)->(qi,z),
d(qj,l,z)->(qk,z),.... với qi là trạng thái kết thúc đầu tiên và qj, qk... là các trạng thái kết thúc còn lại. Sau đó ta gán lại cho qj, qk... thành các trạng thái không kết thúc. Điều kiện 1 đã thỏa.
-Điều kiện 2:
* Đối với các chuyển dịch có dạng:
d(qi,a,A)->(qj,B) tức là thay A trên đỉnh Stack thành B (số phần tử trong stack không đổi)
Với mọi npda luôn có một npda tương ứng thỏa mãn hai điều kiệu sau:. 1.Chỉ có 1 trạng thái kết thúc và npda kết thúc khi stack rỗng.. 2.Mọi chuyển trạng thái đề
Dành riêng cho anh em Ketnooi, bác nào cần download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
NHÓM 13-KHMT1-k2
March 23, 2010
BTL- Môn Automata
2
Chuyển từ một NPDA sang một
văn phạm phi ngữ cảnh.
I.Lý thuyết:
Bổ đề 7.1:
Với mọi npda luôn có một npda tương ứng thỏa mãn hai điều
kiệu sau:
1.Chỉ có 1 trạng thái kết thúc và npda kết thúc khi stack rỗng.2.Mọi chuyển trạng thái đều có dạng:
d(qi,a,A)={c1,c2,...,cn}
trong đó:
ci={qj,
l) (7.5)
hoặc:
ci=(qj,BC) (7.6)
tức là 1 di chuyển hoặc tăng hoặc giảm stack 1 ký hiệu đơn
Bây giờ ta sẽ đi vào chứng minh bổ đề
7.1
bằng cách xây dựng một NPDA
tương đương thỏa mãn 2 điều kiện trên.
-Điều kiện 1:
Giả sử một NPDA có nhiều hơn một trạng thái kết thúc qi,qj,qk.... Ta chuyển hết tất cả các trạng thái kết thúc qj,qk... về trạng thái kết thúc qi khi stack rỗng. Điều này tương đương với việc thêm các chuyển dịch delta như sau vào
d(qj, l,z)->(qi,z),
d(qj,l,z)->(qk,z),.... với qi là trạng thái kết thúc đầu tiên và qj, qk... là các trạng thái kết thúc còn lại. Sau đó ta gán lại cho qj, qk... thành các trạng thái không kết thúc. Điều kiện 1 đã thỏa.
-Điều kiện 2:
* Đối với các chuyển dịch có dạng:
d(qi,a,A)->(qj,B) tức là thay A trên đỉnh Stack thành B (số phần tử trong stack không đổi)
Với mọi npda luôn có một npda tương ứng thỏa mãn hai điều kiệu sau:. 1.Chỉ có 1 trạng thái kết thúc và npda kết thúc khi stack rỗng.. 2.Mọi chuyển trạng thái đề
Dành riêng cho anh em Ketnooi, bác nào cần download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí