Ngôn Ngữ Hình Thức – Wikipedia Tiếng Việt

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:

L1 = {aa, aaa} L2 = {aba, aab} L3 = {ab, ba, aabb,..., aaabbb,...}

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

[sửa | sửa mã nguồn]

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).

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

[sửa | sửa mã nguồn]

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"[1]. 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):

• Loại 0: Recursively Enumerable Languages (ngôn ngữ đếm được theo cách đệ quy)
• Loại 1: Context-Sensitive Languages (ngôn ngữ phụ thuộc ngữ cảnh)
• Loại 2: Context-Free Languages (ngôn ngữ không phụ thuộc ngữ cảnh)
• Loại 3: Regular Languages (ngôn ngữ chính quy)

Các phép toán trên ngôn ngữ

[sửa | sửa mã nguồn]

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:

• Phép nối (concatenation): L1L2 bao gồm tất cả các chuỗi (string) được kết hợp từ 2 ngôn ngữ.
• Phép giao (intersection): L1∩L2 gồm các chuỗi xuất hiện trong cả hai ngôn ngữ.
• Phép bù (complement): ¬L1 hoặc ¬L2 gồm các chuỗi không nằm trong (hoặc thuộc) 2 ngôn ngữ trên.
• Luật Kleene star
• Phép đảo ngược (Reversal):
• Homomorphism trên chuỗi

Ứng dụng

[sửa | sửa mã nguồn]

Ngôn ngữ lập trình

[sửa | sửa mã nguồn]

Ứ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ị...).

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 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

[sửa | sửa mã nguồn]

Trong toán logic, một lý thuyết hình thức (formal theory) là một tập các câu (sentence) được biểu diễn trên một ngôn ngữ hình thức.

Một hệ thống hình thức (hay còn gọi là phép tính logic (logical calculus) hay hệ thống logic (logical system) là sự kết hợp của một ngôn ngữ hình thức và một bộ máy suy diễn (deductive apparatus).

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

[sửa | sửa mã nguồn]

1. ^ “Noam Chomsky on LANGUAGE” (PDF). Bản gốc (PDF) lưu trữ ngày 23 tháng 5 năm 2012. Truy cập ngày 24 tháng 5 năm 2012.

Tham khảo

[sửa | sửa mã nguồn]

• Định nghĩa Ngôn ngữ hình thức, WolframAlpha.
• Bài giảng Ngôn ngữ hình thức và automat[liên kết hỏng], Trường ĐH Hàng Hải.

Các chủ đề chính trong toán học
Nền tảng toán học | Đại số | Giải tích | Hình học | Lý thuyết số | Toán học rời rạc | Toán học ứng dụng | Toán học giải trí | Toán học tô pô | Xác suất thống kê

x t s Chuyên ngành chính của Tin học
Phần cứng • Phần mềm
Công nghệ thông tin	Cuộc sống nhân tạo Đa xử lý Điện toán lưới Đồ họa máy tính Hệ chuyên gia Hệ thống thông tin quản lý Hoạt họa máy tính Khoa học nhận thức Khoa học tính toán Khoa học thần kinh tính toán Khoa học thông tin Kiểm soát song hành Kiến trúc hệ thống Lập luận tự động Ngôn ngữ hình thức Ngôn ngữ học tính toán Người máy Robot học Thực tế ảo Tính toán song song Tối ưu hóa trình biên dịch Tổ chức máy tính Trí tuệ nhân tạo Từ điển học Tương tranh Vật lý học tính toán
Hệ thống thông tin	An toàn thông tin Cơ sở dữ liệu đa phương tiện Cơ sở dữ liệu thông minh Dữ liệu lớn Hệ cơ sở tri thức Hệ dựa trên logic Hệ gợi ý Hệ thích nghi dựa trên ngữ cảnh Hệ thống hướng tác tử Hệ thống thông minh Hệ thống thông tin địa lý Hệ trợ giúp quyết định Kỹ nghệ dữ liệu Kỹ nghệ tri thức Logic mờ Phân tích dữ liệu Phân tích và thiết kế hệ thống Quản trị dự án Quản trị tri thức Thiết kế và quản trị dữ liệu Tích hợp dữ liệu Tính toán hiệu năng cao Web ngữ nghĩa Xử lý thông tin mờ
Khoa học máy tính	Cơ sở dữ liệu phân tán Hệ quản trị cơ sở dữ liệu Hệ thống đa lõi Hệ thống truyền thông Hình học tính toán Hóa học tính toán Học máy Khai phá dữ liệu Lập trình song song Lý thuyết mã hóa Lý thuyết tính toán Ngôn ngữ và phương pháp dịch Nguyên lý ngôn ngữ lập trình Quy hoạch ràng buộc Sinh học tính toán (Tin sinh học) Thiết kế và phân tích thuật toán Tìm kiếm thông tin Tính toán khoa học Tính toán kí hiệu Tính toán phân tán Tính toán tiến hóa Tính toán tự nhiên Tối ưu hoá tổ hợp Xử lý song song
Kỹ thuật máy tính	Đa phương tiện Định vị vệ tinh (GNSS) Giao diện người dùng Ghép nối máy tính Hệ nhúng Hệ thống thời gian thực Hiệu năng hệ thống Kiến trúc máy tính Lập trình đôi Lập trình đồ họa Lập trình hệ thống Lý thuyết nhận dạng Mạng nơ-ron Nhận dạng tiếng nói Phân tích tín hiệu Thị giác máy tính Thiết kế IC Thoại IP Tổng hợp giọng nói Tương tác người–máy tính Vi xử lý Xử lý ảnh Xử lý dữ liệu đa phương tiện Xử lý ngôn ngữ tự nhiên Xử lý tiếng nói Xử lý tín hiệu số
Kỹ nghệ phần mềm	Bảo trì phần mềm Các phương pháp hình thức Chất lượng phần mềm Đảm bảo chất lượng phần mềm Đánh giá phần mềm Đo lường và quản trị phần mềm Độ tin cậy và chịu lỗi phần mềm Kiểm thử phần mềm Kiến trúc doanh nghiệp Kiến trúc phần mềm Kinh tế công nghệ phần mềm Kỹ nghệ hướng dịch vụ Lập trình linh hoạt Mẫu thiết kế Mô hình hóa phần mềm Phân tích hệ thống Phân tích thiết kế hướng đối tượng (UML) Phân tích yêu cầu phần mềm Phát triển phần mềm Quản lý cấu hình phần mềm Quản lý dự án phần mềm Quản lý kỹ thuật phần mềm Quy trình phát triển phần mềm (Vòng đời phát hành phần mềm) Thiết kế phần mềm Triển khai phần mềm Tối ưu hóa phần mềm
Mạng máy tính	An ninh mạng An ninh trong giao dịch điện tử Đánh giá hiệu năng mạng (QoS) Điện toán đám mây Định tuyến Hệ phân tán Kỹ thuật truyền thông Lý thuyết thông tin Mạng không dây Mạng thế hệ mới Mạng thiết bị di động Mạng thông tin quang Mật mã học Mô phỏng mạng Nhận dạng Quản trị mạng Thiết bị truyền thông và mạng Thiết kế mạng Tính toán khắp nơi và di động Trung tâm dữ liệu Truyền thông di động Truyền thông đa phương tiện Truyền thông số Vệ tinh thông tin Viễn thông (Mạng viễn thông) Ước lượng tín hiệu và hệ thống Web thế hệ mới
Tin học kinh tế	x t s Giám đốc công nghệ thông tin · Tin học kinh tế · Quản lý công nghệ thông tin Quản lý ITIL & ITSM Định hướng phát triển Phát triển nhân lực Quản lý bảo mật Quản lý chất lượng Quản lý công nghệ Quản lý dự án Quản lý mua sắm Quản lý ngân sách Quản lý nguồn lực Quản lý phát hành Quản lý rủi ro Quản lý tài sản Quản lý thay đổi Quản lý tích hợp Quản lý tổ chức Quản lý truyền thông Quản lý tuân thủ Quản lý vấn đề Thiết kế giải pháp Xây dựng chiến lược Xây dựng chính sách Quản lý mạng Ảo hóa Mạng campus Mạng diện rộng Mạng nội bộ Mạng riêng ảo STP VLAN IVR VTP Quản trị hệ thống Hoạt động vận hành Bảo trì thiết bị Bảo vệ hệ thống Đối phó sự cố Kế hoạch dự phòng Hoạt động kỹ thuật Hỗ trợ kỹ thuật Kiểm soát truy cập Kiểm tra hệ thống Xác thực người dùng Hoạt động an toàn An ninh nhân sự An ninh hệ thống Nhận thức an toàn Rủi ro hệ thống Quản lý hệ thống Bàn dịch vụ Quản lý cấu hình Quản lý công suất Quản lý dịch vụ Quản lý hạ tầng Quản lý khôi phục Quản lý người dùng Quản lý sự cố Quản lý tính liên tục Quản lý tính sẵn sàng Tổ chức công việc Tổ chức hỗ trợ Kỹ năng lãnh đạo Kỹ năng cộng tác nhóm Kỹ năng đàm phán Kỹ năng giải quyết vấn đề Kỹ năng giao tiếp Kỹ năng gọi thoại Kỹ năng huấn luyện Kỹ năng lắng nghe Kỹ năng phân công ủy thác Kỹ năng phỏng vấn tuyển dụng Kỹ năng quản lý thời gian Kỹ năng tạo động lực Kỹ năng tư duy Kỹ năng thiết kế quy trình Kỹ năng thuyết trình Kỹ năng viết tài liệu kỹ thuật Ứng dụng Chính phủ điện tử Giáo dục trực tuyến Hoạch định tài nguyên doanh nghiệp Kinh doanh điện tử (Mua sắm trực tuyến  · Thương mại điện tử  · Tiếp thị trực tuyến) Kinh doanh thông minh Quản lý quan hệ khách hàng Quản lý tri thức Các lĩnh vực liên quan Kinh tế Luật pháp Tài chính Kế toán Kinh doanh Tổ chức Xã hội Quản lý Quản trị kinh doanh