Mô hình Ôtômát hữu hạn tỏng hệt hống dịch tự động Anh - Việt

- TRẦN THỊ BÍCH LIỄU MÔ HÌNH ÔTÔMÁT HỮU HẠN TRONG HỆ THỐNG DỊCH TỰ ĐỘNG ANH_VIỆT Chuyên ngành: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KỸ THUẬT Chuyên ngành: CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN TS.
- Hà Nội, ngày 18 tháng 10 năm 2015 Trần Thị Bích Liễu Lớp cao học 13BCNTT-VINH_Khóa 2013B Viện CNTT&TT – ĐH Bách Khoa HN 4 DANH MỤC CÁC TỪ VIẾT TẮT VÀ KÍ HIỆU EBMT Dịch máy dựa trên nền ví dụ HMM Mô hình Markov ẩn 5 DANH MỤC BẢNG Bảng 1.1.
- Mô tả hàm.
- Mô tả hàm  ủa ôtômát hữu hạn không đơn định với dịch chuyển.
- Sơ đồ trạng thái mô tả Ôtômát hữu hạn.
- Sơ đồ trạng thái mô tả Ôtômát hữu hạn M.
- Sơ đồ trạng thái tối thiểu hóa ôtômát hữu hạn đơn định.
- Sơ đồ trạng thái của ôtômát hữu hạn đơn định.
- Biểu diễn của xích Markov không có trạng thái đầu và trạng thái.
- Mô hình của bộ phân tích từ vựng cho một ngôn ngữ là tập con của Pascal.
- Mô hình tổng quát cho một hệ EBMT.
- Mô hình hệ thống dịch máy Anh-Việt trên nền ví dụ.
- 7 CHƢƠNG I : MÔ HÌNH ÔTÔMÁT HỮU HẠN.
- 10 1.1 Khái niệm ôtômát hữu hạn.
- Tối thiểu hoá Ôtômát hữu hạn.
- Mô hình Xích Markov [2.
- 19 CHƢƠNG II: ỨNG DỤNG CỦA ÔTÔMÁT HỮU HẠN.
- Mô hình Markov ẩn (Hidden Markov Model) và bài toán gán nhãn từ loại.
- Phƣơng pháp dịch máy trên nền ví dụ.
- Biểu diễn ngữ liệu mẫu trong bài toán dịch máy trên nền ví dụ.
- Tổng quát về hệ thống dịch máy Anh_Việt.
- Lý do chọn đề tài Ôtômát hữu hạn là mô hình được sử dụng trong kỹ thuật cũng như trong tin học.
- Đặc biệt, ôtômát hữu hạn là công cụ hữu hiệu được sử dụng xử lý ngôn ngữ tự nhiên với nhiều bài toán phổ biến : bài toán tách từ, bài toán gán nhãn từ và bài toán dịch máy.
- Mục đích nghiên cứu - Nghiên cứu mô hình ôtômát hữu hạn - Tìm hiểu ứng dụng của ôtômát hữu hạn trong xử lý ngôn ngữ tự nhiên - Nghiên cứu phương pháp xây dựng bộ ngữ liệu tiếng Anh nhờ công cụ ôtômát - Thử nghiệm ứng dụng dịch máy trên nền ví dụ.
- Phạm vi nghiên cứu Luận văn tập trung nghiên cứu mô hình ôtômát hữu hạn và ứng dụng của nó trong các bài toán về xử lý ngôn ngữ tự nhiên.
- Chƣơng 1.Mô hình ôtômát hữu hạn.
- Chương này nghiên cứu về mô hình ôtômát hữu hạn.
- Chƣơng 2.Ứng dụng của ôtômát hữu hạn.
- Chương này nghiên cứu về các ứng dụng của ôtômát hữu hạn như: bài toán gán nhãn từ, bài toán dịch máy.
- Biểu diễn ngữ liệu mẫu trong bài toán dịch máy Anh_Việt.
- Chương này trình bày biểu diễn ngữ liệu mẫu trong bài toán dịch máy Anh_Việt.
- Thử nghiệm hệ dịch máy Anh_Việt.
- 10 CHƢƠNG I : MÔ HÌNH ÔTÔMÁT HỮU HẠN 1.1 Khái niệm ôtômát hữu hạn Lý thuyết ôtômát nghiên cứu mô hình của một loại máy trừu tượng có khả năng tính toán.
- Từ hàng chục năm trước khi máy tính điện tử đầu tiên ra đời, nhà toán học Anh Alan Turing đã đưa ra mô hình máy Turing, cho đến nay mô hình này vẫn được sử dụng để đánh giá khả năng “tính được trên máy.
- Mỗi trạng thái của hệ thống thể hiện sự tóm tắt các thông tin liện quan đến những input đã chuyển qua và xác định các phép chuyển kế tiếp trên dãy input tiếp theo.
- Đặc điểm hoạt động của loại ôtômát này của là thay đổi trạng thái dựa trên trạng thái hiện hành và một “tín hiệu” đưa vào.
- Ôtômát hữu hạn là mô hình hữu hiệu cho cả phần cứng và phần mềm.
- Là công cụ để thiết kế và kiểm tra hoạt động của các mạch logic, đặc biệt là các mạch dãy  Sử dụng phổ biến trong chương trình dịch, đặc biệt là bộ sinh chương trình dịch để phân tích từ vựng, tức là phân chia văn bản chương trình nguồn thành một dãy các từ tố  Là mô hình để xây dựng các hệ phản ứng (reactive system) sử dụng trong kỹ thuật để điều khiển các thiết bị như máy bán hàng tự động, thang máy , máy quay video, lò vi sóng.
- Là mô hình để phân tích các kho văn bản lớn như tập hợp câc trang web, tập hợp các câu mẫu trong hệ thống dịch máy.
- Là mô hình cho các hệ thống xác minh, làm việc với các giao thức truyền thông, nhằm đảm bảo việc truyền tin an toàn trên mạng 11 Vì vậy, lý do quan trọng nhất cho việc nghiên cứu các hệ hữu hạn trạng thái là tính tự nhiên của khái niệm và khả năng ứng dụng đa dạng trong nhiều lĩnh vực thực tế.
- Ôtômát hữu hạn có 2 dạng: ôtômát đoán nhận dùng trong đoán nhận ngôn ngữ và máy chuyển đổi hữu hạn trạng thái với một số thông tin được đưa ra.
- Ôtômát hữu hạn thường được mô tả bằng sơ đồ trạng thái.
- Đó là một đồ thị định hướng với các đỉnh thể hiện các trạng thái (trạng thái đầu có mũi tên chỉ vào, trạng thái kết thúc được biểu diễn bởi vòng tròn kép) và các cung có nhãn là các ký hiệu đưa vào mô tả khả năng chuyển sang trạng thái mới.
- Sơ đồ trạng thái mô tả Ôtômát hữu hạn Xâu w1= 10101 là xâu được M đoán nhận vì khi đọc hết xâu, M chuyển đến trạng thái kết thúc là 1.
- Xâu 010001 không được đoán nhận vì khi đọc hết xâu, M đến trạng thái 4 không phải là trạng thái kết thúc.
- Ôtômát hữu hạn đơn định – DFA ( Deterministic Finite Automata) và không đơn định – NFA ( Deterministic Finite Automata.
- Ôtômát hữu hạn đơn định Một ôtômát hữu hạn đơn định (DFA) gồm một tập hữu hạn các trạng thái và một tập các phép chuyển từ trạng thái này đến trạng thái khác trên các ký hiệu nhập (input symbols) được chọn từ một bộ chữ cái ∑ nào đó.
- Mỗi kí hiệu nhập có đúng một phép chuyển khỏi mỗi trạng thái (có thể chuyển trở về chính nó).
- Một trạng thái, thường kí hiệu là q0 gọi là trạng thái bắt đầu (trạng thái ôtômát bắt đầu).
- 12 Một số trạng thái được thiết kế như là các trạng thái kết thúc hay trạng thái chấp nhận.
- Định nghĩa hình thức Theo [2], một ôtômát hữu hạn đơn định được định nghĩa là một bộ 5: M= (Q.
- Q là tập hữu hạn các trạng thái  Σ là tập hữu hạn ký hiệu, được gọi là bảng chữ vào.
- δ là hàm chuyển trạng thái.
- q0 là trạng thái đầu.
- F là tập trạng thái kết thúc.
- Ví dụ : Mô tả hình thức của ôtômát hữu hạn M với sơ đồ trạng thái ở hình 1.1 M= (Q.
- Mô tả hàm  13 *Ngôn ngữ đoán nhận bởi ôtômát hữu hạn Định nghĩa Ngôn ngữ đoán nhận bởi ôtômát hữu hạn đơn định M = (Q.
- Ôtômát hữu hạn không đơn định Định nghĩa Ôtômát hữu hạn không đơn định là bộ 5 : M.
- qo, F được định nghĩa giống ôtômát hữu hạn đơn định Riêng hàm.
- Hình trạng của ôtômát hữu hạn không đơn định: Được định nghĩa giống hình trạng của ôtômát hữu hạn đơn định.
- Ngôn ngữ đoán nhận bởi ôtômát hữu hạn không đơn định : Cũng định nghĩa giống ngôn ngữ đoán nhận bởi ôtômát hữu hạn đơn định.
- Ví dụ : Ôtômát hữu hạn M’ đoán nhận tập các xâu trên {a, b} tận cùng bằng abb.
- Sơ đồ trạng thái Hình 1.2.
- Sơ đồ trạng thái mô tả Ôtômát hữu hạn M’ Mô tả hình thức M= (Q.
- q0, F) Q a, b} F ={3} Hàm được mô tả bằng bảng  A b .
- Tƣơng đƣơng giữa ôtômát hữu hạn đơn định và không đơn định Ôtômát hữu hạn không đơn định là mô hình trực quan, dễ thiết kế nhưng trong thực tế lập trình do điều kiện thiết bị và để xử lý ngôn ngữ tự nhiên được dễ dàng hơn như nhận dạng một chuỗi, do đó với mỗi ôtômát hữu hạn không đơn định ta có thể xây dựng được một ôtômát hữu hạn đơn định tương đương.
- Định lý : Nếu ngôn ngữ L được đoán nhận bởi ôtômát hữu hạn không đơn định thì tồn tại ôtômát hữu hạn đơn định đoán nhận L.
- Ôtômát hữu hạn với dịch chuyển  Trường hợp đặc biệt của ôtômát hữu hạn không đơn định là ôtômát hữu hạn có dịch chuyển.
- Đó là những ôtômát hữu hạn mà trong sơ đồ trạng thái tồn tại những cung với nhãn.
- Nếu có cung nhãn  từ trạng thái p sang trạng thái q, có thể hiểu hoạt động là Ôtômát hữu hạn ở trạng thái p, đầu đọc chỉ ký hiệu a nào đó sẽ chuyển sang trạng thái q , đầu đọc đứng yên không dịch chuyển.
- Ví dụ : Sơ đồ trạng thái của ôtômát hữu hạn M với dịch chuyển.
- Sơ đồ trạng thái của ôtômát hữu hạn M với dịch chuyển  Định nghĩa: Ôtômát hữu hạn (không đơn định) với dịch chuyển  là bộ 5 : M.
- Mô tả hàm củaôtômát hữu hạn không đơn định với dịch chuyển  1.2.
- Tối thiểu hoá Ôtômát hữu hạn Cực tiểu hóa ôtômát hữu hạn đơn định nghĩa là tìm một ôtômát hữu hạn đơn định tương đương có số trạng thái ít nhất.
- Ôtômát hữu hạn đơn định tối thiểu là duy nhất đối với một ngôn ngữ.
- q0, F ) là ôtômát hữu hạn đơn định.
- Các trạng thái qi và qj là tương đương nếu ˆ(qi, u.
- 16 Các trạng thái tương đương gọi là không phân biệt được.
- Ngược lại, chúng là phân biệt được.Như vậy hai trạng thái qj và qj là phân biệt được nếu tồn tại xâu u sao cho ˆ(qi, u) F và ˆ(qj, u.
- Giải thuật xác định các trạng thái phân biệt của ôtômát hữu hạn đơn định M Tư tưởng chính của giải thuật là xây dựng mảng D[i, j

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt