Tài liệu Xây dựng bộ công cụ thực hiện một số giải thuật trong môn học ngôn ngữ hình thức và Automata

ĐỀ TÀI: Xây dựng bộ công cụ thực hiện một số giải thuật trong môn học ngôn ngữ hình thức và Automata

[FONT=]Môn học ngôn ngữ hình thức và automata có rất nhiều ứng dụng trong lĩnh vực khoa học máy tính như xây dựng các trình biên dịch, nhận dạng và chuyển đổi giữa các ngôn ngữ khác nhau Do đó mà môn học này là một môn học bắt buộc cho các sinh viên ngành CNTT trong các trường đại học.[/COLOR]
[FONT=]
[FONT=]Để giúp cho các sinh viên có điều kiện học tốt và thực hành các bài tập của môn học này, luận văn này đi sâu vào việc mô phỏng lại hoạt động của các giải thuật trong phần ngôn ngữ phi ngữ cảnh đặc biệt là các giải thuật phân tích cú pháp Earley và CYK.
[FONT=]
[FONT=]Sinh viên có thể khai thác cơ sở lý thuyết của môn học thông qua hệ thống Help của chương trình.
[FONT=]
[FONT=]Xin cám ơn thầy Hồ Văn Quân đã tận tình hướng dẫn và giúp đỡ tôi hoàn thành bản luận văn tốt nghiệp như yêu cầu của đề bài.
[FONT=]1. GIỚI THIỆU ĐỀ TÀI[FONT=]
[FONT=]Yêu cầu của đề tài là :
[FONT=]“Xây dựng bộ công cụ thực hiện một số giải thuật trong môn học ngôn ngữ hình thức và Automata.” Ngoài các giải thuật biến đổi văn phạm, tập trung vào nghiên cứu và hiện thực hai giải thuật phân tích cú pháp CYK và Earley, Đánh giá số bước phân tích của mỗi giải thuật.
[FONT=]Aùp dụng nhận dạng một câu nhập thuộc ngôn ngữ tự nhiên (Tiếng Anh)
[FONT=]
[FONT=]2. MỤC ĐÍCH & Ý NGHĨA [FONT=]
[FONT=]Hiện nay, ở nước ta việc áp dụng giảng dạy các môn học thông qua các mô hình giảng dạy thiết kế trên máy tính còn gặp nhiều khó khăn, một trong những nguyên nhân là thiếu các phần mềm hỗ trợ việc học và giảng dạy.
[FONT=]Luận văn này ra đời không nằm ngoài mục đích giúp sinh viên nghành CNTT có một công cụ để hỗ trợ thêm cho việc học môn học “Ngôn Ngữ Hình Thức & Automata” . Bộ công cụ này cho phép sinh thấy rõ cách thức hoạt động của một số giải thuật của phần ngôn ngữ phi ngữ cảnh, cũng như thấy được ứng dụng của các giải thuật phân tích cú pháp.
[FONT=]
[FONT=]3. NỘI DUNG CHÍNH CỦA LUẬN VĂN TỐT NGHIỆP[FONT=][/B]
[FONT=]Nội dung của luận văn được chia làm 8 phần, cụ thể như sau:
¨[FONT=] [FONT=]Phần 1 :[FONT=] Là phần giới thiệu về đề tài, cùng ý nghĩa và tầm quan trọng của nó.
¨[FONT=] [FONT=]Phần 2 :[FONT=] Đây là phần tìm hiểu về cơ sở lý thuyết có liên quan, trong phần 2 này được chia làm 4 chương với các chủ đề tìm hiểu khác nhau cụ thể là :
[FONT=]Chương 1 :[FONT=] Một số khái niệm cơ bản của môn học
[FONT=]Mục đích của chương này là giúp cho người đọc làm quen với một số khái niệm về Ngôn ngữ Hình thức & Automat như chuỗi, ngôn ngữ và văn phạm chính qui, ngôn ngữ và văn phạm PNC, cây dẫn xuất để có thể dễ dàng đọc tiếp những phần sau.Tuy nhiên, người đọc có thể bỏ qua chương này nếu đã nắm được các khái niệm trên.
[FONT=]Chương 2 :Các giải thuật biến đổi văn phạm PNC & các dạng chuẩn[FONT=]
[FONT=]Trong chương này tập trung tìm hiểu các giải thuật biến đổi văn phạm PNC như : Loại bỏ các luật sinh rỗng, đơn vị, vô dụng cũng như chuyển đổi một văn phạm PNC bất kỳ về hai dạng chuẩn Chomsky và Greibach, đây là phần lý thuết cơ bản làm nền tảng cho việc thực hiện giải thuật phân tích cú pháp CYK sau này.
[FONT=]Chương 3 [FONT=]: Trình bày Một số giải thuật và công cụ phân tích cú pháp thông dụng bao gồm phương pháp từ trên xuống (top -down) và từ dưới lên (bootom -up) mục đích là giúp cho người đọc có sơ sở để so sánh với hai giải thuật phân tích cú pháp tổng quát CYK và Earley
[FONT=]Chuơng 4 : Giải thuật phân tích cú pháp Earley và CYK[FONT=], đây là phần chính của luận văn, trong chương này chú trọng đến việc tìm hiểu về giải thuật để phân tích cú pháp và tạo chuỗi dẫn xuất cho câu nhập, cũng như so sánh độ phức tạp của hai giải thuật này với các giải thuật ở chương 3.
¨[FONT=] [FONT=]Phần 3 :[FONT=] Tìm hiểu lý thuyết về phần mềm hỗ trợ học tập và giảng dạy, cách thức để thiết kế và lựa chọn mô hình giảng dạy tốt.
¨[FONT=] [FONT=]Phần 4 :[FONT=] Tập trung phân tích và thiết kế cho mô hình vừa chọn, phần này dựa trên các lý thuyết đã tìm hiểu ở phần 2 và mô hình giảng dạy để đưa ra
·[FONT=] [FONT=]Lựa chọn ngôn ngữ lập trình
·[FONT=] [FONT=]Cấu trúc dữ liệu cho các giải thuật sử dụng trong chương trình
·[FONT=] [FONT=]Cách thức nhập liệu, cấu trúc file lưu trữ
[FONT=tahoma]·[FONT=] [FONT=]Cách trình bày dữ liệu xuất[/FONT]
[COLOR=#363636][FONT=tahoma]·[FONT=] [FONT=]Các lưu đồ thuật toán, tính toán độ phức tạp[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma]·[FONT=] [FONT=][/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma]¨[FONT=] [B][FONT=]Phần 5 : [/B][FONT=]So sánh độ phức tạp giữa hai giải thuật phân tích cú pháp CYK và Earley, trong phần này đưa ra các giả thiết để thực hiện tính độ phức tạp cho hai giải thuật trên bằng chương trình cũng như đưa ra những minh họa bằng ví dụ thực tế (với các đồ thị minh họa)[/FONT][/COLOR][/font][/font][FONT=tahoma][COLOR=#363636][FONT=tahoma][B]
¨[FONT=] [B][FONT=]Phần 6 :[/B][FONT=] Aùp dụng nhận dạng ngôn ngữ tự nhiên, trong phần này sẽ trình bày các vấn đề liên quan đến việc nhận dạng một câu nhập (Tiếng Anh) và cách thức xây dựng bộ từ điển token.[/B][/font][/COLOR][FONT=tahoma][B]
[COLOR=#363636][FONT=tahoma]¨[FONT=] [B][FONT=]Phần 7 :[/B][FONT=] Thiết kế Help : đây cũng là một phần quan trọng của một chương trình trợ giúp học tập, trong phần này chú trọng tìm hiểu thiết kế một hệ thống Help. Đặc biệt là thiết kế hệ thống Help cho chương trình thông qua công cụ Windows Help Designer Pro (down load từ http://www.devgr.com)[/FONT][/COLOR][/B][COLOR=#363636][FONT=tahoma][B]
¨[FONT=] [B][FONT=]Phần 8 :[/B][FONT=] Giới thiệu chuơng trình kết quả.[/B][/font][/COLOR][FONT=tahoma][B]
[COLOR=#363636][FONT=tahoma]¨[FONT=] [B][FONT=]Phần 9 :[/B][FONT=] Phụ lục - Mã chương trình[/FONT][/COLOR][/B][COLOR=#363636][FONT=tahoma][B]
¨[FONT=] [B][FONT=]Phần 10 :[/B] Giới thiệu các tài liệu tham khả[/B][/font][/color][/font][/font][/font]