Bài tập lớn: Lý thuyết ngôn ngữ

BÀI TẬP LỚN: LÝ THUYẾT NGÔN NGỮỨNG DỤNG CỦA VĂN PHẠM VÀ AUTOMATATHÀNH VIÊN NHÓM 4 CÙNG THỰC HIỆN:NGUYỄN NGỌC TÂMNGUYỄN THỊ SENNGUYỄN THỊ SÁNGNGUYỄN THỊ HỒNG THẮMCÙNG SỰ HƯỚNG DẪN CỦA TH.s TRẦN XUÂN SANGGIÁO VIÊN CHUYÊN MÔNPHẦN I:ỨNG DỤNG CỦA AUTOMATA HỮU HẠN TRONG VIỆC PHÂN TÍCH TỪ VỰNG MỞ RỘNGApplications of finite AutomataRepresenting large VocabulariesGIỚI THIỆUCách dùng otomat hữu hạn để mô tả một loạt các từ vựng là một kỹ thuật đã được khẳng định. Có thể ứng dụng mang tính truyền thống. Nó được tìm thấy trong cấu trúc lệnh nơi mà ôtômat có thể được sử dụng để làm mẫu và thực hiện những phân tích từ vựng học mang tính hiệu quả. Ứng dụng của ôtmat hữu hạn để giải quyết một vài vấn đề đặc biệt trong việc xử lý ngôn ngữ tự nhiên là khá phổ biến. Tuy nhiên, ý tưởng gói gọn các “từ vựng mở rộng” vào otomat đơn định và nhiều ứng dụng của nó dường như còn mang tính mới mẻ.Cơ sở để thúc đẩy cho nghiên cứu này là một chương trình kiểm tra lỗi chính tả áp dụng cho hầu hết các ngôn ngữ. Cho ví dụ , chương trình kiểm tra chính tả mà chúng ta đề cập có thể xử lý khoảng 30.000 từ mỗi giây, với automat hơn 200.000 từ đặt vừa khít vào 124 kbytes bộ nhớ.Trong chủ đề này chúng ta sẽ bàn đến chi tiết những vấn đề sau: 1. Thực hiện kiểm tra chính tả dựa trên ôtmat 2. Mô tả thuật toán và cấu trúc dữ liệu được  sử sụng 3. Một vài sự thống kê và đo lường 4. Một vài ứng dụng1. Thực hiện kiểm tra chính tả dựa trên ôtmat Một trong những chương trình kiểm tra chính tả được sử dụng rộng rãi nhất là chương trình UNIX Spell. Chương trình này thực hiện kiểm tra bằng cách loạI bỏ từ được cho khỏi tiền tố của nó, cho ví dụ: Re- work –ed  work và over – tak- ing  take. Bằng cách sử dụng việc loại bỏ tiền tố, từ điển ban đầu khoảng 250.000 từ vựng đã giảm xuống còn 30.000 từ . Tuy nhiên, việc loại bỏ phụ tố( bao gồm tiền tố và hậu tố) có thể dẫn đến việc chấp nhận những từ không tồn tại. Thêm nữa, chương trình kiểm tra sẽ chấp nhận những từ không có nghĩa trong khi kiểm tra chính tả :womans thay vì woman’s( số nhiều của woman là women), tos thay vì toes( hoặc có thể là toss), và toing thay vì toeing( hoặc towing). Để có thê khắc phục những nhược điểm trên , chúng tôi đã quyết định thử một phương pháp khác bằng cách xây dựng một otomat hữu hạn đơn định cục bộ (aminimal acyclic deterministic partial finite automaton) có thể chấp nhận một cách chính xác khoảng 206.000 từ có mặt trong từ vựng. Theo cách này chúng ta có thể tránh được vấn đề đưa vào những từ không tồn tại. Bên cạnh đóHình 1: Otomat đơn định cho tất cả các dạng của các động từ : re work , replay, overwork và overplay Otomat có thể cung cấp một cách đơn giản và chung chung để loại bỏ một cách tuyệt đối các tiền tố và hậu tố vì mỗi trong số chúng sẽ được mô tả duy nhất một lần. Trong hình 1, chúng tôi chỉ ra một otomat cho tất cả các dạng của các động từ tiếng anh rework, replay, overwork and overplay. Chú ý rằng để bao gồm tất cả các dạng của động từ work, chỉ cần thêm duy nhất một chuyển (transition) được gán nhãn bởi chữ cái w từ trạng thái 0  9.Function BuildAutomaton(Vocabulary);Begin A  EmptyAutomaton; Repeat While A not full do Include the next word of Vocabulary in A; A minimal(A) Until no more words in vocabulary; Return A;End; Đây là thuật toán mô tả cách xây dựng otomat của ‘từ vựng’ mở rộng : i. Hai vòng lặp để tăng cường khả năng trong quá trình xử lý nhất là đối với loại ngôn ngữ chứa nhiều từ vựng.ii. Với thuật toán này thì tốc độ cũng như thời gian truy cập từ vựng phụ thuộc vào chiều dài của từ đang được tìm kiếm, mà không phụ thuộc vào kích cỡ của otomat. 2. Cách thực hiện của automata iii. Thuật toán tìm kiếm cho một từ là rất hiệu quả, bắt đầu từ trạng thái đầu tiên nó đi qua otomat bằng cách sử dụng các chữ cái liên tiếp nhau của từ đó để lựa chọn trạng thái chuyển, cho đến khi hoặc một trạng thái kết thúc được đưa ra hoặc không có sự chuyển nào tồn tại(hoặc từ đó thuộc từ vựng hay không) iiii. Từ vựng tiếng anh chứa khoảng 81.000 từ đã tạo ra automata với khoảng 30.000 trạng thái và 68.000 chuyển. Mỗi trạng thái có thể được mô tả bởi một cặp chuyển : một ký tự ( một byte) và một mục trạng thái ( hai bytes) ; một byte phụ cho mỗI trạng thái nắm dữ số lượng các chuyển có mặt. 3. Tìm hiểu một vài thống kế và đo lường Nhiều từ mới được thêm một cách đơn giản từ các từ vựng đã có trong otomat . .Điều này có thể làm otomat được thu nhỏ lại Cho ví dụ, nếu từ overplayed bị loại khỏi otomat trong hinh 1, otomat kết quả sẽ thực sự tăng từ 17 trạng thái và 22 chuyển tới 18 trạng thái và 25 chuyển. Hình2: Otomat chấp nhận tất cả các từ có tối đa là bốn ký tự Trong trường hợp đặc biệt, chúng ta nên nhớ rằng, nếu cho 26 ký tự alphabet, một từ vựng trong tất cả các dãy ký tự có chiều dài tối đa M sẽ có (26M+1-1)/25 từ; cho ví dụ, cho M=4, chúng ta sẽ có 475,225 từ. Mặt khác, otomat cho từ vựng đó chỉ có 27M+1 chuyển đổi (109 đối với M=4; xem hình 2)4. Một vài ứng dụng H ình 3: Cách đánh số của ôtômat Chúng ta thừa nhận rằng, sự mô tả của otomat gồm một số nguyên cái mà đưa ra số lượng của từ được chấp nhận bởi otomat bắt đầu từ trạng thái đó. Chúng ta gọi otomat như vậy được gọi là otomat được đánh số, kiểu như trong hình 4. chúng ta sẽ xây dựng hai hàm liên quan giữa các số từ 1 tới L (L là số lượng các từ được chấp nhận bởi ôtmat) và các từ như sau: được gọi là otomat được đánh số, kiểu như trong hình 4. Chúng ta sẽ xây dựng hai hàm liên quan giữa các số từ 1 tới L (L là số lượng các từ được chấp nhận bởi ôtmat) và các từ như sau: 4.1 Từ điển đa ngôn ngữ Otomat được đánh số có thể được sử dụng để thực hiện từ điển đa ngôn ngữ cho việc chuyển đổi giữa từ và từ. Các từ vựng đối với một vài ngôn ngữ có thể được mô tả bởi một otomat với nhiều trạng thái khởi tạo. Một điều thú vị là, bằng cách đảo ngược các từ trong khi xây dựng otomat, yêu cầu xử lý sẽ tận dụng tối đa sự tồn tại trong việc kiểm tra sự tương đương giữa các ngôn ngữ (tối ưu bộ nhớ), chẳng hạn như các tiền tố và các từ gốc tồn tại trong nhiều ngôn ngữ Châu Âu nói chung. Bên trong ottomat, đối với mỗi ngôn ngữ, chúng ta có thể sử dụng một mảng được đánh số bởi các con số của từ và vẽ chúng vào danh sách được định vị cho ngôn ngữ khác. 4.2 Từ đồng nghĩa Cho một từ 'word', các từ đồng nghĩa của nó bao gồm như sau: work: noun: avocation, calling, employment, field, job, occupation, proffesion, trade, vocation, chore, grind, sweet verb: answer, do, fulfill, meetqualify, suffice Về mặt phạm trù ngữ pháp, từ đó là thuộc về danh từ, động từ. Chúng ta có một chuỗi các danh sách các từ có liên quan, với mỗi danh sách tương xứng với một cách hiểu khác nhau của từ, nếu chúng ta đưa một từ bất kỳ nằm trong một danh sách các từ có liên quan. Kết quả mà chúng ta sẽ nhận được là danh sách các từ đồng nghĩa. Chúng ta thực hiện việc tìm từ đồng nghĩa này bằng cách sử dụng một otomat được đánh số với nhiều trạng thái khởi đầu : mỗi trạng thái phù hợp với một phạm trù ngữ pháp. Bên cạnh đó, chúng ta sử dụng một vài các cấu trúc dữ liệu để mô tả danh sách các từ theo tuần tự các con số. Giả sử, sự thực hiện này được kiểm tra đối với các từ đồng nghĩa tiếng Anh. Otomat của nó chấp nhận khoảng 9.500 từ , có tối thiểu 9.000 trạng thái và 18.000 chuyển.Yêu cầu lưu trữ là 88kbytes cho otomat và khoảng 39kbytes cho cấu trúc dữ liệu 5. Future work Chúng ta có thể thấy rằng otomat đơn định cung cấp một công cụ có ích cho nhiều ứng dụng. Một trong những phương hướng mà họ theo đuổi trong tương lai là làm một vài thử nghiệm trên các ngôn ngữ khác hơn so với tiếng Anh và thử xây dựng Otomat cho từ vựng mở rộng hơn rất nhiều.PHẦN II:AUTOMATA ĐẨY XUỐNGNỘI DUNG CHÍNH:Trong chương này, chúng ta khảo sát một dạng mô hình ôtômát khác, có khả năng nhận diện được lớp ngôn ngữ mà văn phạm phi ngữ cảnh sinh ra - ôtômát đẩy xuống (PDA) - với sự bổ sung thêm của Stack đóng vai trò như một bộ giữ nhớ trong quá trình ôtômát thực hiện các phép chuyển để nhận dạng ngôn ngữ. Tiếp theo đó, mối quan hệ tương đương giữa hai cơ chế - ôtômát đẩy xuống và CFG- dùng biểu diễn cho lớp văn phạm phi ngữ cảnh cũng sẽ được nêu ra và chứng minh chặt chẽMục tiêu cần đạt : Cuối chương này, sinh viên có thể: Thiết kế PDA chấp nhận một ngôn ngữ phi ngữ cảnh cho trước bằng Stack rỗng hay trạng thái kết thúc. Chuyển một PDA chấp nhận ngôn ngữ bằng trạng thái kết thúc sang PDA chấp nhận ngôn ngữ bằng Stack rỗng và ngược lại. Xây dựng NPDA chấp nhận ngôn ngữ sinh ra từ một CFG. Viết văn phạm phi ngữ cảnh sinh ra lớp ngôn ngữ được chấp nhận bởi một NPDA cho trước. ÔTÔMÁT ĐẨY XUỐNG ( PDA : PUSHDOWN AUTOMATA) Như ta đã biết, lớp các ngôn ngữ chính quy được sinh từ văn phạm chính quy, đồng thời cũng được đoán nhận bởi các ôtômát hữu hạn (đơn định hoặc không đơn định). Trong phần này, chúng ta lại thấy một điều tương tự là lớp ngôn ngữ phi ngữ cảnh, được sinh ra từ văn phạm phi ngữ cảnh, cũng được đoán nhận bởi một loại ôtômát khác - gọi là ôtômát đẩy xuống (PDA). Có một điều khác biệt là ở đây, chỉ có dạng ôtômát đẩy xuống không đơn định (NPDA) mới có thể đủ mạnh để đoán nhận lớp ngôn ngữ phi ngữ cảnh, còn dạng đơn định (DPDA) chỉ cho phép đoán nhận một tập con thực sự của lớp ngôn ngữ này. Tuy nhiên, tập con đó cũng bao gồm phần lớn các ngôn ngữ lập trình. 1.1. Mô tả PDA Ôtômát đẩy xuống thực chất là một ôtômát với sự điều khiển cả hai: băng nhập và Stack (bộ đẩy xuống). Về cơ bản, nó vẫn giữ tất cả các thành phần của một ôtômát hữu hạn, với sự bổ sung thêm một ngăn xếp làm việc (Stack) đóng vai trò như một bộ giữ nhớ, nhờ đó mà khả năng ghi nhớ của ôtômát được tăng thêm. Stack xem như là một chồng đĩa, vì vậy cái đặt vào sau sẽ lấy ra trước (LIFO). Với sự mở rộng này ôtômát đẩy xuống có thể chấp nhận cả các biểu thức không chính quy. Chẳng hạn tập hợp L = {wcwR | w ∈ (0+1)*} (với wR là chuỗi đảo ngược của chuỗi w) là một ngôn ngữ phi ngữ cảnh sinh bởi văn phạm S → 0S0 | 1S1 | c và nó không thể được chấp nhận bởi bất kỳ một ôtômát hữu hạn nào. Hình 6.1 - Mô tả một PDA Để chấp nhận ngôn ngữ L như trên ta dùng bộ điều khiển có hai trạng thái q1, q2 và một Stack trên đó ta đặt các đĩa xanh (B), vàng (Y), đỏ (R). Thiết bị sẽ thao tác theo các quy tắc sau đây: 1) Máy sẽ bắt đầu với một đĩa đỏ ở trên Stack và bộ điều khiển ở trạng thái q1.2) Nếu 0 được đưa vào thiết bị thì ta đặt một đĩa xanh vào Stack. Nếu đưa 1 vào thiết bị ở trạng thái q1 thì ta đặt một đĩa vàng vào Stack. Cả hai trường hợp thiết bị không thay đổi trạng thái. 3) Nếu c được đưa vào thiết bị ở trạng thái q1 thì thiết bị đổi trạng thái sang q2 và không thay đổi Stack. 4) Nếu 0 được đưa vào thiết bị ở trạng thái q2 và đỉnh Stack là đĩa màu xanh thì đĩa được lấy ra. Nếu 1 đưa vào thiết bị ở trạng thái q2 và đĩa vàng tại đỉnh Stack thì ta loại bỏ đĩa này. Trạng thái q2 không thay đổi. 5) Nếu thiết bị ở trạng thái q2 và đĩa đỏ tại đỉnh Stack ta loại bỏ đĩa này không cần ký hiệu nhập. 6) Ngoài các trường hợp trên thì thiết bị không thay đổi.Các quy tắc trên được tóm tắt như trong bảng sau:Hình 6.2 - Mô tả hoạt động của PDA chấp nhận ngôn ngữ {wcwR |w∈ (0+1)*} Một chuỗi được chấp nhận bởi thiết bị nếu nó đã đọc duyệt qua đến hết chuỗi đồng thời với Stack trở về trạng thái rỗng. Nhận xét : Nhờ Stack có khả năng lưu giữ một số bất kỳ các ký hiệu mà PDA có thể nhớ nửa phần đầu của chuỗi (w) cho tới khi gặp ký hiệu phân cách c, cho dù chuỗi có độ dài lớn đến bao nhiêu. Và sau đó, các ký hiệu này được đem ra để so sánh dần với phần chuỗi ngược còn lại (wR). Một ôtômát hữu hạn không có được khả năng ghi nhớ đó1.2. Định nghĩa . Kiểu thứ hai không phụ thuộc vào ký hiệu nhập, gọi là ε - dịch chuyển :tương tự như kiểu thứ nhất, chỉ ngoại trừ là ký hiệu nhập không được dùng và đầu đọc không dịch chuyển sau khi chuyển trạng thái. Thực chất, bước chuyển đặc biệt này là một sự tạm ngừng quan sát trên băng nhập để sắp xếp lại các ký hiệu trong ngăn xếp.Ôtômát đẩy xuống có một bộ điều khiển hữu hạn và một Stack. Stack chứa một chuỗi các ký hiệu thuộc một bộ chữ cái nào đó. Ký hiệu bên trái nhất của chuỗi xem như ký hiệu tại đỉnh Stack. PDA không đơn định nếu như có một số hữu hạn các lựa chọn phép chuyển trong mỗi lần chuyển.Phép chuyển sẽ có hai kiểu:P Kiểu thứ nhất phụ thuộc vào ký hiệu nhập, tức là với một trạng thái, một ký hiệu tại đỉnh Stack và một ký hiệu nhập; PDA sẽ lựa chọn trạng thái kế tiếp và một chuỗi các ký hiệu thay thế trên Stack, đầu đọc dịch đi sang phải một ký hiệuCó hai cách để định nghĩa ngôn ngữ chấp nhận bởi ôtômát đẩy xuống: Ngôn ngữ được chấp nhận bởi Stack rỗng: gồm tất cả các input mà sau một chuỗi các phép chuyển trạng thái làm cho ôtômát dẫn tới Stack rỗng. Ngôn ngữ được chấp nhận bởi trạng thái kết thúc: ta thiết kế một số trạng thái kết thúc, khi đó ngôn ngữ chấp nhận bởi ôtômát có thể định nghĩa gồm tất cả các input mà có một chuỗi các phép chuyển làm cho ôtômát dẫn tới một trong những trạng thái kết thúc.