Lý Thuyết Ngôn Ngữ Hình Thức PDF

Thông tin chi tiết

Lý Thuyết Ngôn Ngữ Hình Thức

Trong toán học và khoa học máy tính, một ngôn ngữ hình thức (formal language) được định nghĩa là một tập các chuỗi (string) được xây dựng dựa trên một bảng chữ cái (alphabet), và chúng được ràng buộc bởi các luật (rule) hoặc văn phạm (grammar) đã được định nghĩa trước. Alphabet có thể là tập các ký tự trong ngôn ngữ tự nhiên (natural language) hoặc tập tự định nghĩa các ký tự.

Giả sử có một alphabet ∑ = {a, b} và ký hiệu L là ngôn ngữ. Như vậy, ta có thể định nghĩa một số ngôn ngữ trên alphabet ∑ như sau:

Lĩnh vực mà lý thuyết ngôn ngữ hình thức nghiên cứu là những mẫu hình (pattern) có cấu trúc bên trong những ngôn ngữ hình thức, và đó là những khía cạnh hoàn toàn mang tính chất có cú pháp. Ngôn ngữ hình thức không còn đơn giản chỉ là để định nghĩa ngôn ngữ tự nhiên, mà nó đã vượt ra ngoài khỏi phạm vi đó, và nó cũng là một cách để hiểu được những quy tắc có cú pháp của ngôn ngữ tự nhiên.

Lý thuyết ngôn ngữ hình thức còn được ứng dụng trong lĩnh vực khoa học máy tính, cụ thể là các ngôn ngữ lập trình khi mà mỗi từ của ngôn ngữ đó đều mang một ý nghĩa đặc biệt. Còn trong lĩnh vực lý thuyết độ phức tạp tính toán (Computational complexity theory), các vấn đề quyết định (decision problems) được định nghĩa như là các ngôn ngữ hình thức, và các lớp độ phức tạp (complexity classes) được xác định là tập của những ngôn ngữ hình thức. Còn trong toán học, cú pháp của các hệ thống tiên đề được biểu diễn bằng ngôn ngữ hình thức.