Wikipedia

Khác biệt giữa bản sửa đổi của “Ngôn ngữ hình thức”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Jaselg (thảo luận | đóng góp)
84 sửa đổi
Không có tóm lược sửa đổi
Jaselg (thảo luận | đóng góp)
84 sửa đổi
Không có tóm lược sửa đổi
Dòng 1:
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'') trong [[alphabetbả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 <math>\sum∑ = \{a, b\}</math>. Như vậy, ta có thể định nghĩa nhữngmột số ngôn ngữ trên alphabet ∑ như sau:▼
 
:: L<sub>1</sub> = {aa, aaa}
&:: L_1L<sub>2</sub> = \{aba, aab\} \\▼
&:: L_1L<sub>3</sub> = \{ab, ba, aabb,..., aaabbb,...\}▼
 
▲Giả sử có một alphabet <math>\sum = \{a, b\}</math>. Như vậy, ta có thể định nghĩa những ngôn ngữ trên alphabet ∑ như sau:
::<math>\begin{align}
& L_1 = \{aa, aaa\} \\
▲& L_1 = \{aba, aab\} \\
▲& L_1 = \{ab, ba, aabb,..., aaabbb,...\}
\end{align}</math>
 
==Các định nghĩa==
* '''Chuỗi''' (''string'') hoặc '''từ''' (''word''): là một chuỗi các kí tự trên alphabet nào đó.▼
* '''Alphabet'''
 
▲* '''Chuỗi''' (''string'') hoặc '''từ''' (''word''): là một chuỗi các kí tự 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"''<ref>[http://www.chomsky.info/onchomsky/199812--.pdf ''Noam Chomsky on LANGUAGE'']</ref>. Bằng những nỗinỗ 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''):
Hàng 48 ⟶ 49:
 
Một [[dẫn xuất]] (''derivation'') là một chuỗi hữu hạn các công thức đúng cú pháp.
 
==Chú thích==
{{Reflist}}
 
==Tham khảo==
Hàng 53 ⟶ 57:
* [http://elib.dtu.edu.vn/file/Ebook/3310.pdf Bài giảng ''Ngôn ngữ hình thức và automat''], Trường ĐH Hàng Hải.
 
{{sơ khai}}
{{toán học}}
Lấy từ “https://vi.wikipedia.org/wiki/Ngôn_ngữ_hình_thức”