Bài giảng Ngôn ngữ học máy tính - Nguyễn Tuấn Đăng - Dẫn nhập ngôn ngữ học máy tính

DẪN NHẬP
NGÔN NGỮ HỌC MÁY TÍNH
Nội dung
• Bối cảnh lịch sử
• Định nghĩa ngữ pháp hình thức
• Hệ thống phân loại của Chomsky
Bối cảnh lịch sử
• Năm 1949, Shannon và Weaver xuất bản The
Mathematical Theory of Communication, chỉ ra
rằng các tính toán xấp xỉ theo thống kê cho tiếng
Anh dựa trên các quá trình Markov có thể được
sử dụng để mã hóa hiệu quả tiếng Anh trong
việc truyền tải có nhiễu.
Bối cảnh lịch sử
• Năm 1957, Chomsky xuất bản Syntactic
Structures (Cấu trúc cú pháp), cho thấy rằng
các ngữ pháp tự nhiên không thể được xử lý một
cách chính xác bằng các phương pháp như trên.
• Trong giai đoạn này, hầu hết các cách tiếp cận
đều sử dụng phương pháp biểu diễn symbolic
cho các vấn đề về ngôn ngữ.
Bối cảnh lịch sử
• Khoảng năm 1988, các thử nghiệm cho thấy
phương pháp thống kê gần đúng đã làm
việc tốt hơn so với các phương pháp biểu diễn
symbolic trên hầu như tất cả các nhiệm
vụ, chẳng hạn như nhận dạng tiếng nói, phân
tích văn bản phi cấn trúc và dịch máy.
Bối cảnh lịch sử
• Hầu hết các công việc trong Ngôn ngữ học
Máy tính chuyển sang sử dụng các phương pháp
thống kê gần đúng, máy học.
• Khoảng năm 2000, đặt vấn đề phối hợp ngôn
ngữ học, các mô hình thống kê, và máy học.
Ngữ pháp hình thức
Một ngữ pháp hình thức G gồm bốn thành phần: 
G = 
N: một tập hữu hạn các kí hiệu không kết thúc
T: một tập hữu hạn các ký hiệu kết thúc
S: ký hiệu bắt đầu (S  N)
R: các quy tắc sinh (‘productions’) 
Ngữ pháp hình thức
• Quy tắc có dạng ,
“ rewrites as ”, trong đó ,  là chuỗi ký
hiệu từ tập vô hạn các chuỗi (TN)* và  phải
chứa ít nhất một ký hiệu không kết thúc.
Chomsky Hierarchy
• Một thành phần quan trọng của lý thuyết của
Chomsky là hệ thống các loại ngôn ngữ, nay
được gọi là hệ thống phân cấp Chomsky:
– Mỗi loại đặc trưng bởi một lớp các quy tắc đủ để đặ
tả tất cả ngôn ngữ của loại hình đó,
– Một cơ chế tự động đủ để nhận diện một
câu từ một ngôn ngữ nhất định của loại đó, và
– Những lớp ngôn ngữ ở cấp thấp hơn trong phân cấp.
Chomsky Hierarchy
Loại 0: Không có giới hạn. Mỗi quy tắc có dạng
  , và  ≠.
Loại 1: Mỗi quy tắc có dạng A  , trong
đó A  N và ≠.
Loại 2: Mỗi quy tắc có dạng A  . ( có thể là
.)
Loại 3: Mỗi quy tắc có dạng A aB hoặc A a.
Trong đó: A là ký hiệu không kết thúc; a là ký hiệu kết thúc; α, β và
γ chuỗi các ký hiệu kết thúc và không kết thúc; ε là chuỗi rỗng.
Chomsky Hierarchy
Loại 0: Không hạn chế hệ thống viết lại (máy 
Turing)
Loại 1: Ngữ pháp phụ thuộc ngữ cảnh
Loại 2: Ngữ pháp phi ngữ cảnh
Loại 3: Biểu thức chính qui.
Chomsky Hierarchy