tailieunhanh - Bài giảng Tin học lý thuyết: Chương 4 - Võ Huỳnh Trâm

Bài giảng "Tin học lý thuyết - 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 (RG: egular rammar), 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. . | Printed with FinePrint - purchase at Sự tương đương giữa RG FA BỔ đề bơm cho tập hợp chính quy Đinh ly Nếu L là một tập hợp chính quy thì L được sinh ra từ một văn phạm tuyến tính trái hoặc một văn phạm tuyến tính phải nào đó Ỷ nghĩa một Automata hữu hạn có thể được biểu diễn bởi một văn phạm chính quy. Ví dụ xét DFA cho 0 10 start 1 0 1 Bổ đè nếu L là tập hợp chính quy thì có tồn tại hằng số n sao cho nếu z là một từ bất kỳ thuộc L và zI n thì ta có thể viết z uvw với uv n v 1 và vi 0 ta có uv w e L Chửng minh L là ngôn ngữ chính quy tồn tại DFA M Q z õ q0 F có n trạng thái chấp nhận L. Xét chuỗi nhập z a1a2. .am m n Với mỗi i 1 2 . m ta đặt õ q0 qi Phải có ít nhất 2 trạng thái trùng nhau z G L qm e F a1. ajak 1 .am e L M aj iak e L M với i 0 5 7 Sự tương đương giữa RG FA BỔ đề bơm cho tập hợp chính quy Tuyến tính phái xét hàm chuyển trạng thái ỗ p a q Ta có luật sinh p aq Ngoài ra nếu q là trạng thái kết thúc ta có thêm luật sinh p a Nếu q0 là trạng thái kết thúc thêm vào s q01 A 0B B 0D C 0B D 0D I 1D I 0 I 1D I 0 1D Do biến D không có ích A 0B I 0 B 1C c OB I 0 Tuyến tính trái Bắt đầu với một NFA cho LR Đảo ngược chuỗi vế phải cho tất cả mọi luật sinh của văn phạm vừa thu được ứng dung cúa bổ đễ bcym dùng để chứng tỏ một tập hợp không là tập hợp chính quy Ví du chứng minh tập hợp L 0 I i là số nguyên 1 1 không làp tập hợp chính quy Chửng minh Giả sử L là tập chính quy tồn tại DFA chấp nhận L. 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à uvw e L Xét i 2 ta phải có uv2w e L Mặt khác n2 lzl luvwl luvvwl n2 n n 1 2 Do n2 và n 1 2 là 2 số chính phương liên tiếp nên luv2wl không thể là một số chính phương hay uv2w không thuộc L trái giả thiết . 8 Printed with FinePrint - purchase at Tính chất đóng của tập hợp chính quy 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. Đinh lý .

• Tin học văn phòng
• Văn phạm chính quy
• Bài giảng Tin học lý thuyết
• Văn phạm chính quy
• Tin học lý thuyết
• Sự tương đương giữa RG và FA
• Tập hợp chính quy
• Danh mục văn bản quy phạm
• Văn bản quy phạm pháp luật
• Văn bản quy phạm trung ương
• Các quyền dân sự
• Quyền chính trị
• Văn bản quy phạm
• Biên bản vi phạm hành chính
• Mẫu biên bản vi phạm hành chính
• Biên bản về vi phạm quy chế thi
• Vi phạm quy chế thi
• Mẫu biên bản vi phạm quy chế thi
• Văn bản vi phạm quy chế thi
• Biên bản vi phạm nội quy công ty
• Vi phạm nội quy công ty
• Văn bản vi phạm nội quy công ty
• Mẫu biên bản vi phạm nội quy
• Quy phạm pháp luật hành chính
• Ban hành văn bản luật
• Quy phạm pháp luật
• Quy tắc xử sự
• Quan hệ xã hội
• Cơ quan nhà nước
• Hệ thống văn bản quy phạm pháp luật
• Tài liệu tập huấn kỹ năng lấy ý kiến
• Dự thảo văn bản quy phạm pháp luật
• Phản biện xã hội
• Công tác xây dựng chính sách
• Soạn thảo văn bản quy phạm pháp luật
• Quy định của pháp luật Việt Nam
• Kỹ năng phản biện xã hội
• Văn bản luật hành chính
• Xử lí vi phạm hành chính
• Ban hành văn bản quy phạm pháp luật
• Vi phạm pháp luật
• Quy trình xây dựng văn bản pháp luật
• Quy trình xây dựng dự thảo nghị quyết
• Quy trình xây dựng nghị định
• Quy trình xây dựng luật
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Luật học
• Lịch sử nhà nước và pháp luật
• Xây dựng văn bản quy phạm pháp luật
• Luật ban hành văn bản quy phạm pháp luật
• Văn Bản Luật
• Vi phạm hành chính
• Luật Hiến pháp
• Luật Hành chính
• Xử lý văn bản quy phạm pháp luật
• Kiểm tra văn bản quy phạm pháp luật
• So sánh văn bản hành chính
• Văn bản hành chính thông thường
• Văn bản hành chính
• Luật văn Thạc sĩ Luật học
• Tài liệu về kỹ thuật soạn thảo
• Kỹ thuật soạn thảo quy phạm hành chính
• Soạn thảo quy phạm thủ tục hành chính
• Cải cách hành chính
• Đặc điểm văn bản quy phạm pháp luật
• Kiểm tra văn bản quy phạm
• Toán giải tích
• Bài giảng Toán giải tích
• Tính chất văn phạm chính quy
• Bổ đề bơm
• Chính quyền địa phương
• Hình thức văn bản quy phạm pháp luật
• Quy trình ban hành văn bản pháp luật
• Dự thảo văn bản
• Chỉnh lý dự thảo văn bản
• hành chính nhà nước
• quy phạm hành chính
• bộ luật hành chính
• luật ô nhiễm thủy nội
• Thông tư số 58 2013 TT BGTVT
• Hợp nhất văn bản quy phạm pháp luật
• Kiểm soát thủ tục hành chính
• Luận án Tiến sĩ
• Luận án Tiến sĩ Quản lý công
• Thủ tục hành chính
• Văn bản quy phạm pháp luật của Bộ
• Luận án Tiến sĩ Quản lý hành chính công
• Quản lý hành chính công
• Chính quyền cấp tỉnh
• Văn bản lập quy
• Bố cục của văn bản lập quy
• Nội dung của văn bản lập quy
• Cơ cấu của quy phạm pháp luật
• Cơ quan hành chính nhà nước
• Luật hành chính Việt Nam