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

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

Thêm vào BST

Báo xấu

89
lượt xem 5
download

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

Bài giảng Lý thuyết tính toán: Bài 03 - Ngôn ngữ và văn phạm chính quy hướng đến trình bày những vấn đề cơ bản về biểu thức chính quy; mối quan hệ giữa Biểu thức và ngôn ngữ chính quy; văn phạm chính quy.

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 03 - Nguyễn Ngọc Tú

LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) Bài 03. Ngôn ngữ và Văn phạm 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  Biểu thức chính qui (Regular Expression)  Mối quan hệ giữa Biểu thức và ngôn ngữ chính qui  Văn phạm chính qui (Regular Grammar)
Biểu thức chính quy  Biểu thức chính qui (BTCQ) là gì?  Là một sự kết hợp các chuỗi kí hiệu của một bảng chữ cái ∑ nào đó, các dấu ngoặc, và các phép toán +, ., và *. trong đó phép + biểu thị cho phép hội, phép . biểu thị cho phép kết nối, phép * biểu thị cho phép bao đóng sao.  Ví dụ  Ngôn ngữ {a} được biểu thị bởi BTCQ a.  Ngôn ngữ {a, b, c} được biểu thị bởi BTCQ a + b + c.  Ngược lại BTCQ (a + b.c)* biểu thị cho ngôn ngữ {λ, a, bc, aa, abc, bca, bcbc, aaa, aabc, ...}.
Định nghĩa  Định nghĩa 3.1  Cho ∑ là một bảng chữ cái, thì 1. ∅, λ, và a ∈ ∑ tất cả đều là những BTCQ hơn nữa chúng được gọi là những BTCQ nguyên thủy. 2. Nếu r1 và r2 là những BTCQ, thì r1 + r2, r1. r2, r1*, và (r1) cũng vậy. 3. Một chuỗi là một BTCQ nếu và chỉ nếu nó có thể được dẫn xuất từ các BTCQ nguyên thủy bằng một số lần hữu hạn áp dụng các quy tắc trong (2).
Ví dụ  Cho ∑ = {a, b, c}, thì chuỗi (a + b.c)*.(c + ∅) là BTCQ, vì nó được xây dựng bằng cách áp dụng các qui tắc ở trên. Còn (a + b+) không phải là BTCQ.
Ngôn ngữ tương ứng BTCQ  Định nghĩa 3.2  Ngôn ngữ L(r) được biểu thị bởi BTCQ bất kỳ là được định nghĩa bởi các qui tắc sau. 1. ∅ là BTCQ biểu thị tập trống, 2. λ là BTCQ biểu thị {λ}, 3. Đối với mọi a ∈ ∑, a là BTCQ biểu thị {a}, Nếu r1 và r2 là những BTCQ, thì 1. L(r1 + r2) = L(r1) ∪ L(r2), 2. L(r1.r2) = L(r1).L(r2), 3. L((r1)) = L(r1), 4. L(r1*) = (L(r1))*.
Ngôn ngữ tương ứng BTCQ  Bao đóng sao > Kết nối > Hợp L(a* . a + b) = L(a* . a)L(b) = (L(a* ) L(a))L(b) = ((L(a))* L(a))L(b) = ({, a, aa, aaa, ...}{a}){b} = {a, aa, aaa, ..., b} = {an  n1}{b}
Ex.  Tìm ngôn ngữ của các BTCQ sau  r1 = (aa)*(bb)*b  r2 = (ab*a + b)*  r3 = a(a + b)* Kết quả L(r1) = {a2nb2m+1: n ≥ 0, m ≥ 0} L(r2) = {w ∈ {a, b}*: na(w) chẵn} L(r3) = {w ∈ {a, b}*: w được bắt đầu bằng a}
Ex 02.  Tìm BTCQ cho các ngôn ngữ sau  L1 = {tập tất cả các số thực của Pascal}  L2 = {w ∈ {0, 1}*: w không có một cặp số 0 liên tiếp nào}  L3 = {w ∈ {0, 1}*: n0(w) = n1(w)}
Phép toán mở rộng  Phép chọn lựa r? hoặc [r]  r ? = [r] = (r + λ)  Phép bao đóng dương +  r+ = r.r*  Chú ý  (r*)* = r*  (r1* + r2)* = (r1 + r2)*  (r1r2* + r2)* = (r1 + r2)*  Trong một số tài liệu phép cộng (+) được kí hiệu bằng dấu | thay cho dấu + . Chẳng hạn (a + b).c thì được viết là (a | b).c
BTCQ Biểu thị Ngôn ngữ Chính quy  Định lý 3.1  Cho r là một BTCQ, thì tồn tại một NFA mà chấp nhận L(r). Vì vậy, L(r) là NNCQ.  Bổ đề  Với mọi NFA có nhiều hơn một trạng thái kết thúc luôn luôn có một NFA tương đương với chỉ một trạng thái kết thúc. qf1 tương đương qf1 λ với qf λ qfn qfn
Thủ tục: re-to-nfa  Mọi nfa có thể được biểu diễn bằng sơ đồ M q0 qf q0 q1  q0 q1 a q0 q1
Thủ tục: re-to-nfa L(r1 + r2) M(r1)  q01 qf1  M(r1) hoặc  M(r2)  q02 qf2 M(r2)
Thủ tục: re-to-nfa L(r1.r2)  M(r1)  M(r2)  q01 qf1 q02 qf2 hoặc M(r1) M(r2)
Thủ tục: re-to-nfa L(r1*)  M(r)  q0 qf hoặc q0 qf 
Thủ tục: re-to-nfa  Ví dụ  L((a + bb)*(ba* + )) M1 a L(a + bb) b b M2 a b  L(ba* + ) 
Ex. r9 = (a + -)(n)*(bv + hbv + v)(a + -)(n)* r10 = (p + -)(p + -)(n + -)(n + -)n(p + -)(p + -)s*  r1 = aa* + aba*b* r11 = (mc*d(c+t)*mc*d)* r12 = ((c(p + h)*)d*)*  r2 = ab(a + ab)* (b + aa)  r3 = ab*aa + bba*ab  r4 = a*b(ab + b)*a*  r5 = (ab* + a*b)(a + b*a)* b  r6 = (b + a*)(ba* + ab)*(b*a + ab)  r7 = (abb*bba + baab*a)*(bbaa + abab)*(aaa+bbb)  r8 = (aabb* + bb*aa)(aa*bb* + baab)*
BTCQ cho NNCQ  Đồ thị chuyển trạng thái tổng quát (generallized transition graphs):  Là một ĐTCTT ngoại trừ các cạnh của nó được gán nhãn bằng các BTCQ.  Ngôn ngữ được chấp nhận bởi nó là tập tất cả các chuỗi được sinh ra bởi các BTCQ mà là nhãn của một con đường nào đó đi từ trạng thái khởi đầu đến một trạng thái kết thúc nào đó của ĐTCTT tổng quát (ĐTCTTTQ).
Đồ thị chuyển trạng thái tổng quát a* c*  Hình bên biểu diễn một ĐTCTTTQ. a+b  NN được chấp nhận bởi nó là L(a*(a + b)c*)  Nhận xét  ĐTCTT của một nfa bất kỳ có thể được xem là ĐTCTTTQ nếu các nhãn cạnh được diễn dịch như sau.  Một cạnh được gán nhãn là một kí hiệu đơn a được diễn dịch thành cạnh được gán nhãn là biểu thức a.  Một cạnh được gán nhãn với nhiều kí hiệu a, b, . . . thì được diễn dịch thành cạnh được gán nhãn là biểu thức a + b + . . .  Mọi NNCQ đều ∃ một ĐTCTTTQ chấp nhận nó. Ngược lại, mỗi NN mà được chấp nhận bởi một ĐTCTTTQ là chính qui.
Rút gọn trạng thái của ĐTCTTTQ Rút gọn trạng thái ce*b e ae*d a b trung gian q. ae*b qi q qj qi qj d c ce*d