ngôn ngữ và biểu diễn ngôn ngữ

Tài liệu tham khảo :

John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages and Computation – Addison – Wesley Publishing Company, Inc – 1979 (trang 1 – trang 12).

Hồ Văn Quân – Giáo trình lý thuyết ôtômát và ngôn ngữ hình thức – Nhà xuất bản Đại học quốc gia Tp. Hồ Chí Minh – 2002 (trang 8 – trang 18).

The Chomsky Hierarchy : http://en.wikipedia.org/wiki/Chomsky_hierarchy

Bộ chữ cái (alphabet)

Một bộ chữ cái (bộ ký hiệu) là một tập hợp không rỗng, ký hiệu là Σ. Các phần tử của một bộ chữ cái Σ được gọi là các ký hiệu (symbol).

Thí dụ 2.1: Bộ chữ cái Latinh {A, B, C, ... , Z, a, b, c, ... , z}

Bộ chữ cái Hylạp {α, β, γ size 12{γ} {}, …, φ}

Bộ chữ số thập phân {0, 1, 2, ... , 9}

Bộ ký hiệu Moene { . , / , - }

Bộ bit nhị phân { 0, 1}

Ký hiệu và chuỗi

Một ký hiệu (symbol) là một thực thể trừu tượng mà ta sẽ không định nghĩa được một cách hình thức.

Chẳng hạn : Các chữ cái (a, b, c, ...) hoặc con số (0, 1, 2, ...) là các ký hiệu.

Một chuỗi (string) hay từ (word) trên bộ chữ cái Σ là một dãy hữu hạn gồm một số lớn hơn hay bằng không các ký hiệu của Σ, trong đó một ký hiệu có thể xuất hiện vài lần.

Chẳng hạn : . a, b, c là các ký hiệu còn abcac là một từ.

. ε, 0, 1011, 00010, ... là các từ trên bộ chữ cái Σ = {0, 1}

Độ dài của một chuỗi w, ký hiệu |w| là số các ký hiệu tạo thành chuỗi w.

Chẳng hạn: Chuỗi abca có độ dài là 4 , ký hiệu : |abca | = 4

Chuỗi rỗng (ký hiệu ε) là chuỗi không có ký hiệu nào, vì vậy | ε | = 0.

Chuỗi v được gọi là chuỗi con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong chuỗi w.

Chẳng hạn: Chuỗi 10 là chuỗi con của chuỗi 010001

Tiền tố của một chuỗi là một chuỗi con bất kỳ nằm ở đầu chuỗi và hậu tố của một chuỗi là chuỗi con nằm ở cuối chuỗi. Tiền tố và hậu tố của một chuỗi khác hơn chính chuỗi đó ta gọi là tiền tố và hậu tố thực sự.

Chẳng hạn: Chuỗi abc có các tiền tố là a, ab, abc và các hậu tố là c, bc, abc

Chuỗi nối kết (ghép) từ hai chuỗi con là một chuỗi tạo được bằng cách viết chuỗi thứ nhất sau đó là chuỗi thứ hai (không có khoảng trống ở giữa).

Chẳng hạn : Nối kết chuỗi Long và Int là chuỗi LongInt.

Sự đặt cạnh nhau như vậy được sử dụng như là một toán tử nối kết. Tức là, nếu w và x là hai chuỗi thì wx là sự nối kết hai chuỗi đó. Chuỗi rỗng là đơn vị của phép nối kết, vì ta có εw = wε = w với mọi chuỗi w.

Ta viết v⁰ = ε ; v¹ = v ; v² = vv ... hay tổng quát vⁱ = vv^{i - 1} với i > 0.

Chuỗi đảo ngược của chuỗi w, ký hiệu w^R là chuỗi w được viết theo thứ tự ngược lại, nghĩa là nếu w = a₁ a₂ ... a_n thì w^R = a_n a_n-1 ... a₁. Hiển nhiên : ε^R = ε

Ngôn ngữ (Languages)

Một ngôn ngữ (hình thức) L là một tập hợp các chuỗi của các ký hiệu từ một bộ chữ cái Σ nào đó.

Tập hợp chứa chuỗi rỗng (ký hiệu {ε}) và tập hợp rỗng ∅ cũng được coi là ngôn ngữ. Chú ý rằng hai ngôn ngữ đó là khác nhau: ngôn ngữ ∅ không có phần tử nào trong khi ngôn ngữ {ε} có một phần tử là chuỗi rỗng ε.

Tập hợp tất cả các chuỗi con kể cả chuỗi rỗng trên bộ chữ cái cố định Σ, ký hiệu là Σ^* cũng là một ngôn ngữ. Mỗi ngôn ngữ trên bộ chữ cái Σ đều là tập con của Σ^*. Chú ý rằng Σ^* vô hạn đếm được với mọi Σ khác ∅, vì ta có thể liệt kê tất cả các chuỗi con của nó theo thứ tự độ dài tăng dần, khi có cùng độ dài thì liệt kê theo thứ tự từ điển.

Ngoài ra tập hợp tât cả các chuỗi sinh ra từ bộ chữ cái Σ, ngoại trừ chuỗi rỗng ε, được ký hiệu là Σ⁺. Dễ thấy:

Σ⁺ = Σ^* - {ε} hay Σ^* = Σ⁺ + {ε}

Thí dụ 2.2 : Σ = {a} thì Σ^* = {ε, a, aa, aaa, ...}

Σ⁺ = {a, aa, aaa, ...}

Σ = {0, 1} thì Σ^* = {ε, 0, 1, 00, 01, 10, 11, 000, ...}

Σ⁺ = {0, 1, 00, 01, 10, 11, 000, ...}

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

Từ các ngôn ngữ có trước, ta có thể thu được các ngôn ngữ mới nhờ áp dụng các phép toán trên ngôn ngữ. Trước hết, vì ngôn ngữ là một tập hợp, nên mọi phép toán trên tập hợp như: hợp (union), giao(intersection) và hiệu (difference) ... đều có thể áp dụng lên các ngôn ngữ. Ngoài ra, còn có thêm một số phép toán thường gặp khác như sau :

Phép phần bù (complement) của một ngôn ngữ L trên bộ chữ cái Σ được định nghĩa như sau :

với chú ý khái niệm bù của ngôn ngữ được định nghĩa dựa trên Σ^*

Phép nối kết (concatenation) của hai ngôn ngữ L₁ trên bộ chữ cái Σ₁ và L₂ trên bộ chữ cái Σ₂ được định nghĩa bởi :

L₁L₂ = {w₁w₂ | w₁∈ L₁ và w₂ ∈ L₂ } trên bộ chữ cái Σ₁  Σ₂

Ký hiệu Lⁱ được mở rộng để dùng cho phép nối kết nhiều lần (còn gọi là phép lũy thừa trên chuỗi) trên cùng một tập ngôn ngữ L, tổng quát : Lⁱ = LL^{i - 1}. Theo định nghĩa, ta có một trường hợp đặc biệt : L⁰ = {ε}, với mọi ngôn ngữ L.

Phép bao đóng (closure) : Trong nhiều trường hợp, người ta muốn thành lập một ngôn ngữ bằng cách nối kết các chuỗi (với số lượng bất kỳ) lấy trong một ngôn ngữ L cho trước, các phép toán đó như sau :

Bao đóng (Kleene) của ngôn ngữ L, ký hiệu L^* được định nghĩa là hợp của mọi tập tích trên L :

Bao đóng dương(positive) của ngôn ngữ L, ký hiệu L⁺ được định nghĩa là hợp của mọi tích dương trên L :

Chú ý rằng : L⁺ = lL^* = L^*L

L^* = L⁺ size 12{ union } {} {ε}

Thí dụ 2.3 : Cho ngôn ngữ L = { a, ba } thì

L² = { aa, aba, baa, baba, … }

L³ = { aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa, … }

L^* = { ε, a, ba, aa, aba, baa, baba, aaa, aaba, abaa, ababa, baaa, baaba, … }