BÀI TẬP LỚN:
LÝ THUYẾT NGÔN NGỮ
ỨNG DỤNG CỦA VĂN PHẠM
VÀ AUTOMATA

THÀNH VIÊN NHÓM 4 CÙNG THỰC HIỆN:
1. NGUYỄN NGỌC TÂM
2. NGUYỄN THỊ SEN
3. NGUYỄN THỊ SÁNG
4. NGUYỄN THỊ HỒNG THẮM
CÙNG SỰ HƯỚNG DẪN CỦA
TH.s TRẦN XUÂN SANG
GIÁO VIÊN CHUYÊN MÔN

PHẦN I:
ỨNG DỤNG CỦA AUTOMATA
HỮU HẠN TRONG VIỆC PHÂN
TÍCH TỪ VỰNG MỞ RỘNG
Applications of finite Automata
Representing large Vocabularies

GIỚI THIỆU
Cá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à

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)

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ó (26
M+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ử

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ỐNG

NỘ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.
-

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 = {wcw
R
| w ∈
(0+1)
*
} (với w
R
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 q
1
, q
2
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.