TAILIEUCHUNG - 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

Bài giảng chương 3 trình bày về automata hữu hạn và biểu thức chính quy. Chương này gồm có những nội dung chính sau: 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 & 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 Chương 3: Định nghĩa ôtômát (automata) Định nghĩa: là máy trừu tượng có cơ cấu và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữ Con người phải lập trình sẵn cho máy một ‘lộ trình’ để thực hiện Bộ điều khiển INPUT OUTPUT BỘ NHỚ Phân loại automata Automata đơn định (Deterministic Automata): Mỗi bước di chuyển chỉ được xác định duy nhất bởi cấu hình hiện tại (hàm chuyển của automata là đơn trị) Automata không đơn định (Non-deterministic Automata): Tại mỗi bước di chuyển, nó có vài khả năng để lựa chọn (hàm chuyển của automata là đa trị) Phân loại FA FA (Finite Automata) DFA Deterministic Finite Automata NFA Nondeterministic Finite Automata Biểu thức chính quy Start 1 1 0 0 0 0 1 1 a b c d q1 q0 q3 q2 Ví dụ: Input Bộ điều khiển 1 0 1 0 0 1 1 0 Q : tập hữu hạn các trạng thái (p, q ) Σ : bộ chữ cái nhập (a, b ; w, x, y ) δ : hàm chuyển, ánh xạ: Q x Σ → Q q0 Q : trạng thái bắt đầu. F Q : tập các trạng thái kết thúc. M=(Q, Σ, δ, q0, F) Trạng thái bắt đầu Trạng thái kết thúc x Phép chuyển trên nhãn x Automata hữu hạn đơn định (DFA) Mở rộng hàm chuyển trạng thái δ(q, ) = q δ(q, wa) = δ( δ(q,w), a) với w, a Ngôn ngữ được chấp nhận: L(M) = { x

Hòa Hợp 69 34 ppt

Upload

Không thể tạo bản xem trước, hãy bấm tải xuống

Tải xuống

TÀI LIỆU LIÊN QUAN

Bài giảng 1 giới thiệu môn học Lý thuyết thông tin: - Nguyễn Phương Thái

9 179 5

BÀI GIẢNG MÔN HỌC VỀ LÝ THUYẾT THÔNG TIN

63 188 5

Giáo trình: Lý thuyết thông tin

95 147 5

Giáo trình về lý thuyết thông tin

228 109 0

Đề thi lý thuyết bảng A khối Tiểu học môn Tin học

5 128 2

Đề thi học kì 2 môn Tin học lớp 6 năm 2018 có đáp án (Lý thuyết) - Trường THCS Phú Đa

4 181 2

Đề cương ôn tập lý thuyết nghề Tin học năm học 2017-2018

13 132 0

Giáo án Tin học lớp 7 - Tiết 73: Kiểm tra học kì 2 (Lý thuyết)

6 141 0

Giáo án Tin học lớp 7 - Tiết 37: Kiểm tra học kì 1 (Lý thuyết)

6 124 0

Lý thuyết Tin học lớp 10 – Bài 9: Tin học và xã hội

4 83 1

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 462343 61

Giới thiệu :Lập trình mã nguồn mở

14 26104 79

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11350 542

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10553 466

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9844 108

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8891 1161

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8507 426

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 8101 2279

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 7765 1793

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 7274 268

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

báo cáo hóa học:" Perceptions of rewards among volunteer caregivers of people living with AIDS working in faith-based organizations in South Africa: a qualitative study"

10 157 1 28-12-2024

BÀI GIẢNG Biến Đổi Năng Lượng Điện Cơ - TS. Hồ Phạm Huy

137 161 1 28-12-2024

CHƯƠNG 2: RỦI RO THÂM HỤT TÀI KHÓA

28 160 1 28-12-2024

Sử dụng mô hình ARCH và GARCH để phân tích và dự báo về giá cổ phiếu trên thị trường chứng khoán

24 1073 2 28-12-2024

Báo cáo y học: "The Factors Influencing Depression Endpoints Research (FINDER) study: final results of Italian patients with depressio"

9 151 1 28-12-2024

Báo cáo nghiên cứu khoa học " NÂNG QUAN HỆ KINH TẾ THƯƠNG MẠI VIỆT NAM - TRUNG QUỐC LÊN TẦM CAO THỜI ĐẠI "

8 174 1 28-12-2024

The Ombudsman Enterprise and Administrative Justice

309 143 0 28-12-2024

Sáng kiến kinh nghiệm môn mỹ thuật

5 175 1 28-12-2024

Lịch sử Trung Quốc 5000 năm tập 3 part 2

54 153 1 28-12-2024

Báo cáo lâm nghiệp: "Assessment of the effects of below-zero temperatures on photosynthesis and chlorophyll a fluorescence in leaf discs of Eucalyptus globulu"

4 140 0 28-12-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 8101 2279

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 7765 1793

Ebook Chào con ba mẹ đã sẵn sàng

112 4409 1371

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 6305 1268

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8891 1161

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3843 680

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3920 609

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4719 565

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11350 542

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4511 490