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
n replaced: kí → ký (8) using AWB
Dòng 1:
[[Hình:Automata finito.png|nhỏ|220px|''Tiền đề trong việc xây dựng lý thuyết Automata là 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íký tự trong [[ngôn ngữ tự nhiên]] (''natural language'') hoặc tập tự định nghĩa các kíký tự.
 
Giả sử có một alphabet ∑ = {a, b} và kí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<sub>1</sub> = {aa, aaa}
Dòng 13:
 
==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í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íký tự ∧, ¬, ∀, (,),... ra còn có vô số x<sub>1</sub>, x<sub>2</sub>,... 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 đó.
Dòng 19:
'''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íký hiệu: ∅). Cần phân biệt ''ngôn ngữ rỗng'' và ''[[Chuỗi trống|chuỗi rỗng]]'' (không chứa kíký tự nào trong alphabet).
 
==Phân loại ngôn ngữ theo mô hình Chomsky==
Dòng 45:
Ứ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í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===
Lấy từ “https://vi.wikipedia.org/wiki/Ngôn_ngữ_hình_thức”