Bài giảng Lý thuyết tính toán: Bài 04 - Nguyễn Ngọc Tú

Chia sẻ: Nguyễn Thị Huyền | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

92
lượt xem 5
download

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

Các tính chất của ngôn ngữ chính quy là nội dung bài 4 thuộc "Bài giảng Lý thuyết tính toán" tập trung vào tính đóng của ngôn ngữ chính quy; các câu hỏi cơ bản về ngôn ngữ chính quy; nhận biết các ngôn ngữ không chính quy. Mời các bạn cùng tìm hiểu và tham khảo nội dung thông tin tài liệu.

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 Lý thuyết tính toán: Bài 04 - Nguyễn Ngọc Tú

LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) Bài 04. Các tính chất của Ngôn ngữ Chính quy Sử dụng slides của các tác giả: Hồ Văn Quân + Nick Hopper GV: Nguyễn Ngọc Tú TIN331 Tu.NguyenNgoc@hoasen.edu.vn
Nội dung  Tính đóng của ngôn ngữ chính qui.  Các câu hỏi cơ bản về ngôn ngữ chính qui..  Nhận biết các ngôn ngữ không chính qui
Tính Chất Của Ngôn Ngữ Chính Qui  L1 và L2 là chính qui.  Có thể nói gì về L1∪L2, L1∩L2 , L1●L2 , 𝐿1, L1* ?
Định Lý 1  Nếu L1 và L2 là chính qui thì L1∪L2, L1∩L2 , L1●L2 , 𝐿1, L1* cũng là chính qui.  Họ các ngôn ngữ chính qui là đóng đối với các phép toán giao, hợp, kết nối, lấy phần bù và bao đóng-sao.
Chứng Minh  L1 = L(r1) . L2 = L(r2)  L(r1 + r2) = L(r1)∪L(r2)  L(r1 . r2) = L(r1)L(r2)  L(r1*) = (L(r1))*
Chứng Minh  M = (Q,∑, σ, q0, F) chấp nhận L1.  M = (Q, ∑, σ, q0, Q – F) chấp nhận 𝐿1.
Chứng Minh  M1 = (Q, , 1, q0, F1)  M2 = (P, , 2, p0, F2) a1 an q0 qf 1(qi, a) = qk a1 an p0 pf 2(pj, a) = pl 1((qi, pj), a) = (qk, pl)
Chứng Minh  Chứng minh khác: L1∩L2= L1∩L2=𝐿1 ∪ 𝐿2  Ví dụ: L1 = {abn | n  0} L2 = {anb | n  0} L1L2 = {ab}
Định Lý 2  Họ các ngôn ngữ chính qui là đóng đối với các phép toán hiệu và nghịch đảo: L2 chính qui  L1- L2 cũng chính qui  L 1,  L chính qui  LR cũng chính qui  Chứng minh ?
Đồng Hình (Homomorphism)  Giả sử ∑ và ϓ là các bảng chữ cái.  h: ∑ϓ  được gọi là một phép đồng hình
 Ảnh đồng hình của một chuỗi: w = a1a2 ... an  h(w) = h(a1)h(a2) ... h(an)  Nếu L là một ngôn ngữ trên ∑ thì ảnh đồng hình của nó (homomorphic image) được định nghĩa:  h(L) = {h(w): w ∈ L}
Ex.  = {a, b}  = {a, b, c} h(a) = ab .h(b) = bbc h(aba) = abbbcab L = {aa, aba}  h(L) = {abab, abbbcab}
Đồng Hình  Nếu r là một biểu thức chính qui trên , thì ảnh đồng hình của nó là một biểu thức chính qui h(r) đạt được bằng cách áp dụng phép đồng hình đối với mỗi ký hiệu trên  của r.  = {a, b},  = {b, c, d} h(a) = dbcc h(b) = bdc r = (a + b*)(aa)* h(r) = (dbcc + (bdc)*)(dbccdbcc)*
Định lý 3  Họ các ngôn ngữ chính qui là đóng đối với phép đồng hình:  Nếu L chính qui thì h(L) cũng chính qui  Chứng minh:  Giảsử r là biểu thức chính qui sao cho L(r) = L.  Cần chứng minh: h(L(r)) = L(h(r)).
Thương Đúng (Right Quotient)  Giả sử L1 và L2 là các ngôn ngữ trên cùng một bảng chữ cái. Thì thương đúng của L1 với L2 được định nghĩa là:  L1/L2 = {x | xy ∈ L1 và y ∈ L2}
Ex . L1 = {anbm | n  1, m  0}{ba} L2 = {bm | m  1} L1/L2 = {anbm | n  1, m  0}
Ex . L1 = {anbm | n  1, m  0}{ba} a b a b q0 q1 q2 b a q3 q5 a a, b a, b q4
Định Lý  Họ các ngôn ngữ chính qui là đóng đối với phép thương đúng:  Nếu L1 và L2 chính qui thì L1/L2 cùng chính qui.
Chứng Minh  M = (Q, , , q0, F)  L1 . M^ = (Q, , , q0, F^)  L1/L2.  y  L2 ; *(qi, y)  F  qi và F^  Mi = (Q, , , qi, F) và L(Mi)  L2  .
Ex. Tìm L1/L2 cho L1 = L(a*baa*), L2 = L(ab*). a a a a M1 b a L1/L2 b a q0 q1 q2 q0 q1 q2 b M2 a p0 p1