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

Bài giảng "Tin học lí thuyết - Chương 3: Automata hữu hạn và biểu thức chính quy" cung cấp cho người học các kiến thức: Khái niệm DFA & NFA, sự tương đương giữa DFA & NFA, biểu thức chính quy, các tính chất của tập chính quy. . | Chương 3 Automata hữu hạn Biểu thức chính quy Nòi dung Khái niệm DFA NFA Sự tương đương giữa DFA NFA Biểu thức chính quy Các tính chất của tập chính quy Automata hữu hạn đơn định DFA 0 1 1 0 0 1 0 1 Bộ diều khiển o Trạng thái bắt đầu Trạng thái kết thúc Ví dụ x Phép chuyển trên nhãn x M Q z õ q0 F 1 Q tập hữu hạn các trạng thái p q. z bộ chữ cái nhập a b . w x y . ỗ hàm chuyển ánh xạ Q x z Q q0 e Q trạng thái bắt đầu. F G Q tập các trạng thái kết thúc. 3 Phân loại FA Mở rộng hàm chuyền trạng thái 1. õ q e q 2. õ q wa õ S q w a với V w a Ngôn ngữ điPơc chắp nhân L M x 5 q0 x c F 2 Ví du chuỗi nhập w 110101 QSinh w õ qo 1 q1 õ q0 11 õ q1 1 qo õ q0 110 õ q1 10 õ q0 0 q2 õ q0 1101 õ q1 101 õ q0 01 õ q2 1 q3 õ q0 11010 . õ q3 0 q1 õ q0 110101 . õ qn 1 q0 e F 4 Printed with FinePrint - purchase at Giải thuật hình thức Định nghĩa NFA Muc đích kiểm tra một chuỗi nhập X có thuộc ngôn ngữ L M được chấp nhận bởi automata M. Input chuỗi nhập x Output câu trả lời YES hoặc NO Giải thuât q q0 c nextchar c là ký hiệu nhập được đọc tiếp theo While c do begin q 5 q c c nextchar end If q in F then write YES else write NO M Q z õ q0 F Q tập hữu hạn các trạng thái. z bộ chữ cái nhập. ỗ hàm chuyển ánh xạ Q x z 2Q q0 e Q trạng thái bắt đầu. F G Q tập các trạng thái kết thúc. Chú ỷ khái niệm õ q a là tập hợp tất cả các trang thái p sao cho có phép chuyển từ trạng thái q trên nhãn a. Hàm chuyển trang thái mờ rông ỗ q e q S q wa p I có một trạng thái r trong ỗ q w mà pGỖ r a õ 5 q w a Õ P w oqeP õ q w với cQ 5 Automata hữu hạn không đơn định NFA Ví dụ về NFA Ví du cho automata M hình vẽ và xét chuỗi nhập 01001 Start Ví du xét chuỗi nhập w 01001 và NFA đã cho ở trên M q0 qn q2 q qj 0 1 5 q0 q2 q4 Nhận xét Ứng với một trạng thái và một ký tự nhập có thể có không môt hoặc nhiều phép chuyển trạng thái. DFA là một trường hợp đặc biệt của NFA Õ Input Trạng thái 0 1 q0 q0 q3 q1 0 q2 q2 q2 q2 q3 q4 0 q4 q4 q4 Do q4t F nên w 01001 G L M õ qo 0 qo q3 õ q0 01 õ õ qo 0 1 õ q0 q3

• Tin học văn phòng
• Bài giảng Tin học lí thuyết
• Tin học lí thuyết
• Automata hữu hạn
• Biểu thức chính quy
• Sự tương đương
• Tập chính quy
• 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
• Quy trình thực tập
• Tìm kiếm ứng viên
• Nội quy công ty
• Quy chế công ty
• Quy định đào tạo hội nhập
• Chế độ người lao động
• Chính sách người lao động
• Mục tiêu công ty
• Quyết định tiếp nhận thực tập
• Bản cam kết thực tập
• Đánh giá kết quả thực tập
• quy luật khách quan
• tư tưởng chính trị
• đường lối lãnh đạo
• ôn tập chính trị
• lý thuyết chính trị
• bài thi chính trị
• hướng dẫn ôn tập chính trị
• Hướng dẫn thực tập tốt nghiệp
• Thực tập Quản trị tài chính
• Hồ sơ thực tập Quản trị tài chính
• Quy trình thực tập Quản trị tài chính
• Mục tiêu thực tập Quản trị tài chính
• Biểu mẫu thực tập Quản trị tài chính
• Toán giải tích
• Bài giảng Toán giải tích
• Văn phạm chính quy
• Tính chất văn phạm chính quy
• Bổ đề bơm
• Tập hợp chính quy
• Sự tương đương giữa RG và FA
• Tin học lý thuyết
• Bài giảng Tin học lý thuyết
• Regular Grammar
• Ngôn ngữ chính quy
• Khoa học giáo dục
• Xã hội học tập
• Hệ thống giáo dục suốt đời
• Học tập suốt đời
• Cộng đồng học tập
• Chính sách phát triển xã hội học tập
• Bài giảng Tin học
• Khái niệm DFA
• Sự tương đương giữa DFA và NFA
• TÍnh chất của tập chính quy
• Phân tích báo cáo tài chính
• Báo cáo tài chính
• Báo cáo thường niên
• Quy trình sản xuất khép kín
• Giá trị từ qui mô
• Tổng quan về tập đoàn Hòa Phát
• Quản lý bưu chính
• Ebook Quản lý bưu chính
• Dịch vụ bưu chính
• Quy trình khai thác bưu gửi
• Quản lý chất lượng bưu chính
• Quy hoạch quản lý bưu chính
• Quy luật lượng – chất
• Chương trình giáo dục chính trị
• Đổi mới phương pháp học tập
• Cải thiện môi trường học tập
• Quá trình học tập của sinh viên
• Giải thuật xây dựng hàm
• Luật hành chính
• Quản lý nhà nước
• Câu hỏi ôn tập luật hành chính
• Ôn tập luật hành chính
• Quy phạm pháp luật hành chính
• Quan hệ pháp luật hành chính
• quy chế tuyển sinh đại học
• phạm vi điều chỉnh áp dụng
• đối tượng áp dụng
• quy trình ra đề thi
• công bố điểm trúng tuyển
• bài báo cáo thực tập
• quy luật giá trị
• nền sản xuất hàng hoá
• kinh tế thị trường
• kinh tế xã hội
• quản lý nhà
• Cơ sở quy hoạch
• quy hoạch kiến trúc
• quy hoạch đô thị
• Chuyên đề thực tập
• Hoàn thiện quy trình kiểm toán thuế
• Khoản mục thuế giá trị gia tăng
• Kiểm toán tài chính
• Thuế giá trị gia tăng
• Chuyên đề thực tập tốt nghiệp Kiểm toán
• Kiểm toán khoản mục nợ phải thu
• Khoản mục nợ phải thu khách hàng
• Quy trình kiểm toán Báo cáo tài chính
• Đặc điểm khoản nợ phải thu
• Tóm tắt Luận văn Thạc sĩ Kế toán
• Quy trình hợp nhất báo cáo tài chính
• Công ty cổ phần tập đoàn Mai Linh
• Đông Bắc Bộ
• Nghị định của Chính phủ
• Nghị định Số 93 2002NĐ CP
• Bổ sung Nghị định số 196 CP
• Hướng dẫn thi hành Bộ luật Lao động
• Quy định chi tiết về Bộ luật Lao động
• Thỏa ước lao động tập thể
• Hướng dẫn giải bài tập toán rời rạc
• Bài tập toán rời rạc
• Ngôn ngữ hình thức
• Văn phạm và ôtômat
• Đồ thị và ứng dụng
• Xây dựng mô hình xã hội học tập
• Phát triển giáo dục
• Giáo dục chính quy
• Giáo dục không chính quy
• Phổ cập giáo dục
• Giáo trình Thực tập thành lập bản đồ địa hình
• Thực tập thành lập bản đồ địa hình
• Công tác biên tập bản đồ số
• Quy trình công nghệ biên tập bản đồ địa chính
• Bình sai lưới tứ giác trắc địa
• Sơ đồ chia mảnh bản đồ địa chính