Ngôn ngữ hình thức

Ngôn ngữ hình thức là một dạng tổng quát hoá của khái niệm ngôn ngữ mà ta quen dùng trong đời sống hằng ngày.

Các khái niệm cơ bản

Để bắt đầu, có thể hình dung ngôn ngữ hình thức như một ngôn ngữ thông thường, chẳng hạn tiếng Việt. Một ngôn ngữ như vậy gồm những gì? Ngôn ngữ đó gồm các từ, và ta ghép các từ thành câu. Ở đây ta không quan tâm đến câu, chỉ quan tâm đến từ. Từ được tạo nên từ đâu? Từ các chữ cái của bảng chữ cái. Vì vậy, ta bắt đầu từ bảng chữ cái.

Bảng chữ cái là một tập hợp khác rỗng bất kì. Các phần tử của bảng chữ cái gọi là kí hiệu. Với tiếng Việt, đó là bảng chữ cái tiếng Việt quen thuộc gồm cả chữ thường lẫn chữ hoa, cùng các chữ có dấu. Nếu ta không muốn mô tả tiếng Việt mà muốn mô tả các số chẳng hạn, bảng chữ cái sẽ gồm 10 chữ số. Bảng chữ cái thường kí hiệu là Σ.

Xâu (trong lí thuyết ngôn ngữ hình thức còn gọi là từ, hay chuỗi kí tự) là một dãy hữu hạn các kí hiệu của một bảng chữ cái Σ nào đó. Chẳng hạn, với bảng chữ cái Σ= {a,b,c,d,e,…, z}, các dãy “chao” hay “toan” là xâu, nhưng “việt” thì không (bảng chữ cái không có chữ “ệ”), “Nam” cũng không (không có chữ “N”), “xin chao” cũng không (không có dấu cách). Độ dài của xâu là số kí hiệu tạo nên xâu đó.

Phép ghép xâu: cho hai xâu a = a₁a₂… a_n và b = b₁b₂… b_m. Ghép hai xâu này ta được xâu ab = a₁a₂… a_nb₁b₂… b_m. Ví dụ: ghép hai xâu “chao” và “toan” ta được xâu “chaotoan”. Phép ghép kí hiệu bằng dấu tròn nhỏ, tức là a ∘ b, hoặc không dùng kí hiệu nào cả mà chỉ viết các xâu liền nhau.

Xâu rỗng kí hiệu là ε, đó là xâu có độ dài bằng 0. Ghép xâu a = a₁… a_n với xâu rỗng ε, ta lại được xâu a, tức là a ∘ ε = a.

Bao đóng của bảng chữ cái Σ là tập hợp tất cả các xâu có thể tạo được từ bảng chữ cái Σ, kể cả xâu rỗng. Bao đóng kí hiệu là Σ^∗. Với bảng chữ cái nhị phân Σ= {0, 1}, ta có

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Đôi khi ta còn dùng bao đóng dương của bảng chữ cái, cũng gồm tất cả các xâu tạo được từ bảng chữ cái nhưng không có xâu rỗng. Bao đóng dương kí hiệu là Σ⁺ và Σ⁺ = Σ^∗ ∖ {ε}.

Ví dụ về bảng chữ cái

• Quay lại ví dụ về tiếng Việt. Mọi từ tiếng Việt đều nằm trong bao đóng của bảng chữ cái gồm chữ thường, chữ hoa và các chữ có dấu (có thể thêm dấu gạch nối “-”). Nếu thêm vào bảng chữ cái này dấu cách và các dấu câu (dấu phẩy, dấu chấm, dấu chấm than, dấu chấm hỏi, …), thì bao đóng sẽ chứa mọi câu có thể viết bằng tiếng Việt. Tất nhiên, bao đóng này cũng chứa cả những “câu” như “sadflsf kasdf kagrjewiờảđặấẹýker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”.

• Nếu bảng chữ cái gồm tất cả các chữ số Σ= {0, 1, …, 9}, thì bao đóng chứa mọi số tự nhiên – và còn thêm một số xâu khác. Đó là các xâu bắt đầu bằng chữ số 0, chẳng hạn 00054, và ngoài ra còn có xâu rỗng, tất nhiên xâu rỗng không phải là số nào cả.

• Bảng chữ cái phải khác rỗng, nên bảng chữ cái nhỏ nhất có ít nhất một kí hiệu. Chẳng hạn, với bảng chữ cái Σ= {!} ta được bao đóng Σ^∗ = {ε, !, !!, !!!, !!!!, …}, tức là tập hợp các xâu mà với mỗi n ∈ ℕ, bao đóng có đúng một xâu gồm n dấu chấm than và không có xâu nào khác.

• Cho Σ= {qw,c}. Đây là một bảng chữ cái rất lạ, vì chứa xâu qw. Cách viết này thường không dùng vì dễ gây nhầm lẫn, nhưng có thể hình dung là ta dán hai chữ “q” và “w” lại với nhau thành một kí tự. Khi đó xâu “qw” được xem là kí hiệu “qw”. Nếu từ kí hiệu này ta tạo xâu “qwcqw”, thì xâu đó có độ dài 3 – nó gồm các kí hiệu “qw”, “c” và “qw”. Những bảng chữ cái kiểu này không thường gặp, nhưng có những tình huống ta cần dùng các kí hiệu được ghép từ nhiều kí hiệu như vậy.

Ngôn ngữ hình thức

Ngôn ngữ (hình thức) trên bảng chữ cái Σ là một tập con bất kì của Σ^∗. Như vậy, với ngôn ngữ L trên bảng chữ cái Σ ta có L ⊆ Σ^∗. Ví dụ về ngôn ngữ:

• Ở phần trước ta đã xét bảng chữ cái gồm các chữ số Σ= {0, 1, …, 9}. Bao đóng của bảng chữ cái này là tất cả các xâu chỉ gồm chữ số. Nếu thêm quy tắc xâu không được bắt đầu bằng chữ số 0 và không được rỗng, ta được tập hợp ℕ^* các số tự nhiên khác 0. Vì ℕ^* ⊆ Σ^∗ nên ℕ^* là một ngôn ngữ trên bảng chữ cái Σ.

• Ta có thể thêm vào tập các chữ số trên dấu trừ “-”, khi đó Σ= {0, 1, …, 9, −}. Bao đóng gồm tất cả các xâu tạo bởi chữ số hoặc dấu trừ. Điều đó có nghĩa là bao đóng chứa cả những xâu như “12-84-”, “1-5-8” hay “-”. Để có ngôn ngữ các số nguyên ℤ, ta thêm ba quy tắc:

  • Dấu trừ hoặc không xuất hiện trong xâu, hoặc chỉ xuất hiện ở đầu xâu.
  • Chữ số đầu tiên của xâu không được là 0, trừ xâu “0”.
  • Mỗi xâu phải chứa ít nhất một chữ số.

  Tập hợp này mô tả tập các số nguyên và là tập con của Σ^∗ – do đó đây là một ngôn ngữ trên bảng chữ cái Σ.

• Cho Σ= {0, 1}. Bao đóng gồm tất cả các xâu tạo bởi các chữ số 0 và 1. Ngôn ngữ L trên bảng chữ cái này có thể định nghĩa, chẳng hạn, là tập hợp tất cả các xâu có đúng ba chữ số 1. Ta cũng có thể sáng tạo hơn: ngôn ngữ L là tập hợp tất cả các xâu biểu diễn một tệp docx hợp lệ (tệp mà Word lưu ra).

• Vẫn với bảng chữ cái nhị phân Σ= {0, 1}. Mọi xâu kí tự (các kí tự thông thường có trên bàn phím) đều có thể chuyển sang dạng nhị phân, tức là thành dãy các chữ số 0 và 1, và chuyển ngược lại, chẳng hạn nhờ bảng mã ASCII (nói chính xác hơn, bảng mã ASCII chuyển kí tự thành số, còn số trong hệ thập phân có thể chuyển sang hệ nhị phân). Như vậy, ta có thể định nghĩa ngôn ngữ gồm tất cả các xâu là địa chỉ email hợp lệ, và đó vẫn là một ngôn ngữ trên bảng chữ cái nhị phân.

Phép ghép ngôn ngữ: ta cũng có thể ghép các ngôn ngữ. Định nghĩa tương tự như tích Descartes của các tập hợp. Cho hai ngôn ngữ L₁ và L₂. Ghép chúng, ta được ngôn ngữ mới L₁ ∘ L₂, định nghĩa như sau:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

Tức là ta lấy mọi xâu của ngôn ngữ L₁ và ghép với mọi xâu của ngôn ngữ L₂. Ví dụ: cho

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,chao\}\end{array}$$

Khi đó:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0chao,1a,1b,1chao\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,chao0,chao1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Cho đến giờ ta mô tả ngôn ngữ bằng lời thông thường, tức là nói bằng lời ngôn ngữ trông như thế nào. Cách này rất bất tiện, vì vậy người ta đưa ra những cách hình thức hơn để định nghĩa một ngôn ngữ. Cách đầu tiên là văn phạm.