1295221
Ngôn ngữ hình thức
https://vi.wikipedia.org/wiki?curid=1295221
Title: 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.
Các định nghĩa.
Một alphabet, trong ngữ cảnh ngôn ngữ hình thức thì có thể bất kì tập hợp nào, mặc dù thông thường là tập các chữ cái, hoặc ký tự trong bảng ASCII được sử dụng. Hơn nữa, một alphabet có thể là vô hạn ("infinite"); ví dụ, một tập alphabet ngoài các ký tự ∧, ¬, ∀, (,)... ra còn có vô số x1, x2... thể hiện các biến. Các thành phần riêng lẻ trong một alphabet được gọi là chữ cái ("letter").