1295221
Ngôn ngữ hình thức
https://vi.wikipedia.org/wiki?curid=1295221
Title: Ngôn ngữ hình thức
Chuỗi ("string") hoặc từ ("word"): là một chuỗi các chữ cái trên alphabet nào đó.
Câu ("sentence"): một chuỗi được gọi là "câu" nếu nó thuộc về một ngôn ngữ nào đó.
Ngôn ngữ rỗng ("empty language"): một ngôn ngữ không chứa bất kì câu nào được gọi là "ngôn ngữ rỗng" (ký hiệu: ∅). Cần phân biệt "ngôn ngữ rỗng" và "chuỗi rỗng" (không chứa ký tự nào trong alphabet).
Phân loại ngôn ngữ theo mô hình Chomsky.
Noam Chomsky (1928), một nhà triết học người Mỹ về ngôn ngữ và là giáo sư ngôn ngữ học tại MIT đã xây dựng lên một ý tưởng rằng "Loài người học ngôn ngữ không phải bắt đầu từ những hành vi (behavior) (là những phản ứng sự kích thích một cách có định hướng), mà nó dựa trên nhận thức và sự bẩm sinh". Bằng những nỗ lực để chứng minh học thuyết này, ông đã đưa ra một mô hình gọi là Mô hình phân cấp Chomsky.
Mô hình này gồm bốn loại ngôn ngữ và các gắn kết về ngữ pháp ("grammar") và máy ("machine"):
Các phép toán trên ngôn ngữ.
Giả sử tồn tại L1 và L2 là 2 ngôn ngữ trên một hoặc nhiều bộ alphabet nào đó. Ta có thể thực hiện một số phép tính giữa L1 và L2 như sau:
Ứng dụng.
Ngôn ngữ lập trình.
Ứng dụng thường thấy trong lĩnh vực khoa học máy tính của ngôn ngữ hình thức là Trình biên dịch hay trong các giải thuật về chuỗi (tìm kiếm, hoán vị...).