Vấn đề biểu diễn ngôn ngữ

Như đã định nghĩa ở trên, một ngôn ngữ L trên một bộ chữ cái Σ là một tập con của tập Σ^*. Vậy vấn đề đặt ra là đối với một ngôn ngữ L, làm sao có thể chỉ rõ các chuỗi có thuộc vào L hay không ? Đó chính là vấn đề biểu diễn ngôn ngữ .

Đối với các ngôn ngữ hữu hạn, để biểu diễn chúng một cách đơn giản ta chỉ cần liệt kê tất cả các chuỗi thuộc vào chúng.

Chẳng hạn : L₁ = {ε}

L₂ = { a, ba, aaba, bbbbb }

Tuy nhiên, trong trường hợp các ngôn ngữ là vô hạn, ta không thể liệt kê tất cả các chuỗi thuộc ngôn ngữ được mà phải tìm cho chúng một cách biểu diễn hiệu quả khác.

Trong những trường hợp không phức tạp lắm, người ta thường xác định các chuỗi bằng cách chỉ rõ một đặc điểm chủ yếu chung cho các chuỗi đó. Đặc điểm này thường được mô tả qua một phát biểu hay một tân từ.

Chẳng hạn : L₃ = { aⁱ | i là một số nguyên tố }

L₄ = { aⁱ b^j | i ≥ j ≥ 0 }

L₅ = { w ∈ { a, b}^* | số a trong w = số b trong w }

Song, trong phần lớn các trường hợp, người ta thường biểu diễn ngôn ngữ một cách tổng quát thông qua một văn phạm hay một ôtômát. Văn phạm là một cơ chế cho phép sản sinh ra mọi chuỗi của ngôn ngữ, trong khi ôtômát lại là cơ chế cho phép đoán nhận một chuỗi bất kỳ có thuộc ngôn ngữ hay không. Về mặt hình thức, cả văn phạm và ôtômát đều là các cách biểu hiện khác nhau của cùng một quan niệm.

Thí dụ 2.4 : Cho L là một ngôn ngữ trên bộ chữ cái Σ = {a, b} được định nghĩa như sau:

i) ε ∈ L

ii) Nếu X∈ L thì aXb ∈ L

iii) Không còn chuỗi nào khác thuộc L

Định nghĩa đệ quy trên cho ta một cách sản sinh ra các chuỗi thuộc ngôn ngữ L như sau : Do (i) nên ta có chuỗi đầu tiên trong L là ε. Xem đó là X thì theo (ii) ta lại có được chuỗi thứ hai aεb hay ab. Áp dụng lặp đi lặp lại quy tắc (ii) ta lại tìm được các chuỗi: aabb, rồi lại aaabbb, … Cứ như thế có thể phát sinh tất cả các chuỗi thuộc ngôn ngữ L. Bằng cách áp dụng (một số hữu hạn) quy tắc phát sinh như trên, ta có thể phát sinh bất kỳ chuỗi nào trong ngôn ngữ.

Dễ dàng nhận thấy : L = {aⁱ bⁱ | i ≥ 0}

Trong giáo trình này, chúng ta sẽ tập trung nghiên cứu hai dạng hệ phát sinh dùng để biểu diễn ngôn ngữ, như đã nói ở trên, là văn phạm và ôtômát. Bằng cách ấn định các dạng khác nhau vào các quy tắc phát sinh, người ta cũng định nghĩa nhiều loại văn phạm và ôtômát khác nhau, từ đơn giản đến phức tạp, nghiên cứu các ngôn ngữ sản sinh hay đoán nhận bởi chúng và mối liên quan giữa chúng với nhau.