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 Tin học: Chương 4 - Võ Huỳnh Trâm

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:3

Báo xấu

90
lượt xem 6
download

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

Bài giảng "Tin học - Chương 4: Văn phạm chính quy và các tính chất" cung cấp cho người học các kiến thức: Văn phạm chính quy, sự tương đương giữa RG và FA, bổ đề bơm cho tập hợp chính quy, tính chất đóng của tập hợp chính quy. 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 Tin học: Chương 4 - Võ Huỳnh Trâm

Nếu L ñược sinh ra từ một văn phạm chính quy thì L là tập hợp chính quy Ý h : một văn phạm chính quy có thể ñược biểu diễn bởi ĩ n g a một Automata hữu hạn. • Văn phạm chính quy (RG: egular rammar) xét văn phạm tuyến tính phải: S → 0A ; A → 10A | ε • Sự tương ñương giữa RG và FA à $ N A l b i • t α →α u m n : • Bổ ñề bơm cho tập hợp chính quy • Nếu a là một ký hiệu kết thúc: α α • Tính chất ñóng của tập hợp chính quy • Trạng thái bắt ñầu , trạng thái kết thúc ε 0 ε S t t [S] [0A] [A] [ε] a r ε 1 1 [10A] 3 là văn phạm mà tất cả các luật sinh xét văn phạm tuyến tính trái: S → S10 | 0 của nó ñều có dạng (hoặc / ă h ? í h á • ð ư 4 t t t i → tuyến tính phải o n g c n p : m n n v u y r ) S → 01S | 0 • Tuyến tính trái: dạng A → Bw hoặc A → w 1 • Tuyến tính phải: dạng A → wB hoặc A → w ε 0 S t t [S] [01S] [1S] a r V h h í h ô h í h b i h h í h ă t n p m c n q u y n g n n g c n q u y u c c n , , ε à h h í h : t q u y v p p c n q u y [0] 0 [ε] • Văn phạm chính quy sinh ra ngôn ngữ chính quy / • ð ư 4 t t o n g c a o m a a u • Ngôn ngữ chính quy có thể ñược ký hiệu ñơn giản bằng một biểu thức chính quy 0 ε 1 S t t [ε] [0] [S] [1S] a r • Tập hợp các chuỗi ñược ký hiệu bởi một biểu thức 0 ε chính quy ñược gọi là tập hợp chính quy 2 [01S] 4 Printed with FinePrint - purchase at www.fineprint.com
nếu L là tập hợp chính quy thì có tồn tại hằng số Nếu L là một tập hợp chính quy thì L ñược sinh sao cho nếu là một từ bất kỳ thuộc L và ≥ thì ta có ra từ một văn phạm tuyến tính trái hoặc một văn phạm i thể viết với , và ∀ ta có ∈ tuyến tính phải nào ñó Ý h : một Automata hữu hạn có thể ñược biểu diễn bởi ĩ n g a • L là ngôn ngữ chính quy → tồn tại DFA M=(Q, Σ, δ, q0, F) có một văn phạm chính quy. n trạng thái chấp nhận L. • Xét chuỗi nhập z = a1a2…am, m ≥ n xét DFA cho • Với mỗi i=1,2,…,m, ta ñặt δ(q0, a1a2…ai) = qi 1 • Phải có ít nhất 2 trạng thái trùng nhau 0 A B C S t t • z ∈ L → qm ∈ → a1…ajak+1…am ∈ L(M) → a r 0 i 1 0 1 ∈ , với i ≥ 0 1 j j 1 k k 1 + + m a a j 1 k + . . D 0, 1 a a a a 1 j k 1 . . . + . . m qj=q q q q 5 7 0 m m k xét hàm chuyển trạng thái dùng ñể chứng tỏ một tập hợp không là tập hợp chính quy ó l h • p→ T t i a c u s n : i2 à à ó 0 l h á k h ú h ê l • chứng minh tập hợp N i t t i t t t t t g o r a n u q r n g c a c m u , , không làp tập hợp chính quy h i → s n : • Nếu q0 là trạng thái kết thúc, thêm vào: → 0 • Giả sử L là tập chính quy → tồn tại DFA chấp nhận L. A→ Do biến D không có ích: Gọi n là số trạng thái của DFA. → → n2 → → • Xét chuỗi z = 0 → → • Theo bổ ñề bơm: z=uvw với 1≤ lvl ≤ n và uviw ∈ L • Xét i = 2, ta phải có uv2w ∈ L • Mặt khác: n2 = lzl = luvwl < luvvwl ≤ n2 + n < (n+1)2 • Bắt ñầu với một NFA cho LR • Do n2 và (n+1)2 là 2 số chính phương liên tiếp nên • ðảo ngược chuỗi vế phải cho tất cả mọi luật sinh của luv2wl không thể là một số chính phương, hay uv2w 6 8 văn phạm vừa thu ñược không thuộc L (trái giả thiết). Printed with FinePrint - purchase at www.fineprint.com
Một phép toán là ñóng ñối với tập chính quy khi áp dụng chúng vào tập hợp chính quy thì vẫn giữ ñược các tính chất của tập chính quy. tập hợp chính quy ñóng với các phép toán: hợp, nối kết và bao ñóng Kleen. tập hợp chính quy ñóng với phép lấy phần bù. tập hợp chính quy ñóng với phép giao 9 Printed with FinePrint - purchase at www.fineprint.com

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.