Đồ án, luận văn, do an, luan van

Biểu thức chính quy: Sử dụng các toán tử chính quy để biểu diễn một biểu thức mô tả ngôn ngữ Ví dụ: (0∪1)0* → Tất cả các xâu bắt đầu bằng 1 ký tự 0 hoặc 1 và sau đó là một số nào đó các ký tự 0 • Vai trò của Biểu thức chính quy: Là một phương pháp mạnh để mô tả 1 mẫu văn bản nào đó → Trong một số ngôn ngữ lập trình đều ứng dụng kỹ thuật mô ...

29 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 354 | Lượt tải: 0

Ngôn ngữ chính quy: Ngôn ngữ được đoán nhận bởi một DFA nào đó → Ngôn ngữ không chính quy là gì? Ví dụ: Xét các ngôn ngữ sau trên bộ chữ Σ= {0,1} là chính quy hay không chính quy B = {0n1n|n ≥ 0} C = {w| w có số ký hiệu 0 bằng số ký hiệu 1} D = {w| w có số lần xuất hiện xâu con 01 và 10 là bằng nhau}

18 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 360 | Lượt tải: 0

Khái niệm • Văn phạm phi ngữ cảnh = Context-free Grammar (CFG) • CFG: Là một phương pháp mạnh hơn để mô tả ngôn ngữ • Ứng dụng: - Bộ biên dịch trong các ngôn ngữ lập trình - Bộ phân tích trong các trình biên dịch và thông dịch • Ví du: E → E + T | T T → T × F | F F → (E) | a

30 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 377 | Lượt tải: 0

Ôtômat đẩy xuống = Push down automata (PDA) • PDA: Là một mô hình tính toán, giống với NFA ngoại trừ một thành phần mở rộng được gọi là ngăn xếp • Ngăn xếp: Là một cấu trúc dữ liệu hoạt động theo cơ chế LIFO - Các phương thức: read + push / ignored, pop/ignored • PDA ⇔ CFG về sức mạnh → Thêm công cụ hữu ích khi đoán nhận một ngôn ngữ phi ngữ...

27 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 642 | Lượt tải: 0

Máy Turing = Turing Machine (TM) • TM: - Được đề xuất đầu tiên vào năm 1936 bởi Alan Turing - Là một mô hình tính toán mạnh hơn PDA và FSM - Là một mô hình chính xác hơn rất nhiều của máy tính đa năng - Tương tự như DFA nhưng có một bộ nhớ vô hạn và không hạn định

24 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 365 | Lượt tải: 0

Một giải thuật là tập các lời chỉ dẫn đơn giản để thực hiện một vài nhiệm vụ nào đó • Giải thuật = thủ tục = công thức • Giải thuật đóng vai trò quan trọng cho rất nhiều nhiệm vụ khác nhau Ví dụ: tìm số nguyên tố, tìm ước số chung lớn nhất,. . . • Trước thế kỉ XX, chưa tồn tại khái niệm giải thuật (các khái niệm mang tính trực giác về giải t...

20 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 279 | Lượt tải: 0

Tính quyết định giúp chúng ta nghiên cứu kỹ hơn về khả năng giải quyết các bài toán của thuật toán • Một số bài toán có thể giải được bằng thuật toán, một số thì không thể → Cần phải nghiên cứu về khả năng không giải quyết được • Mục đích là để phát hiện ra giới hạn về tính giải được của thuật toán

21 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 303 | Lượt tải: 0

Bài 1: Cho bộ chữ Σ= {a,b} a. Hãy đưa ra biểu đồ trạng thái của NFA đoán nhận ngôn ngữ tương đương với biểu thức chính quy b*ab*ab* b. Mô tả định nghĩa hình thức của NFA trên c. Hãy đưa ra biểu đồ trạng thái của DFA tương đương với NFA trên và mô tả định nghĩa hình thức d. Hãy mô tả ngôn ngữ mà NFA trên đoán nhận

5 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 338 | Lượt tải: 0

Nội dung bài giảng 1. Giới thiệu 2. Các bài toán không quyết định được 3. Quy dẫn thông qua lịch sử tính toán 4. Bài toán PCP 5. Quy dẫn ánh xạ

35 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 299 | Lượt tải: 0

Tập hợp • Tập hợp: Là tập các đối tượng không trùng lặp VD: N = {1, 2, 3, . . .}, Z = {. . . , −2, −1, 0, 1, 2, . . .} • Biểu diễn: - Liệt kê: D = {a, b, c, d} - Mô tả đặc tính D = {x| x là một ngày trong tháng 9} - Biểu đồ Venn:

32 trang | Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 306 | Lượt tải: 0