Khác biệt giữa bản sửa đổi của “Ngôn ngữ hình thức”
Nội dung được xóa Nội dung được thêm vào
←Trang mới: “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…” |
Không có tóm lược sửa đổi |
||
Dòng 13:
* '''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ỗi 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 4 loại ngôn ngữ và các gắn kết về ngữ pháp (''grammar'') và máy (''machine''):
* Loại 0: Recursively Enumerable Languages
* Loại 1: Context-Sensitive Languages
* Loại 2: Context-Free Languages
* Loại 3: Regular Languages
==Các phép toán trên ngôn ngữ==
Hàng 28 ⟶ 38:
==Ứ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
Một trình biên dịch về cơ bản gồm 2 thành phần riêng biệt. Một là [[trình phân tích từ vựng]] (''lexical analyser''), nó có nhiệm vụ xác định các [[token]] của của nguồn một chương trình máy tính, ví dụ như các [[định danh]] (''identifier'') (tên của hàm, biến...), các [[từ khóa]] (''keyword''), các kí hiệu... Thành phần thứ 2 là [[trình phân tích cú pháp]] (''parser'') với nhiệm vụ quyết định xem mã nguồn chương trình đó có được viết đúng cú pháp của ngôn ngữ lập trình mà trình biên dịch đó hỗ trợ không. Kết quả của một parser là [[cây cú pháp trừu tượng]] (''abstract syntax tree'') và nó được sử dụng cho các giai đoạn sau của quá trình biên dịch. Hai thành phần đó đều hoạt động dựa trên ''ngôn ngữ hình thức''.
===Lý thuyết và hệ thống và dẫn xuất về hình thức===
| |||