Ngôn ngữ hình thức - 2

Xâu x  được gọi là xâu con của xâu w nếu x được tạo từ các ký tự nằm liền kề nhau trong xâu w.

Tiền tố của xâu w là một xâu con bất kỳ nằm ở đầu xâu w. Hậu tố của xâu w là một xâu con bất kỳ nằm ở cuối xâu w.

Ví dụ: cho các xâu w = abc và x = de trên bảng chữ cái La tinh;

- |w| = 3; |x| = 2.

- Các xâu a, b, c, ab, bc, abc là các xâu con của xâu w.

- Các xâu a, ab, abc là các tiền tố của xâu w.

- Các xâu c, bc, abc là các hậu tố của xâu w.

1.1.4. Các phép toán trên xâu

1) Phép nhân ghép hai xâu

Có thể bạn quan tâm!

• Ngôn ngữ hình thức - 1
• Tính Chất 5 (Tính Đệ Quy Của Ngôn Ngữ)
• Văn Phạm Chính Quy Và Automat Hữu Hạn
• Biểu Diễn Automat Bằng Đồ Thị

Xem toàn bộ 254 trang tài liệu này.

Cho hai xâu x = x1x2…xn và y = y1y2…ym trên bảng chữ cái , phép nhân ghép hai xâu x và y là phép cho ta một xâu xy = x1x2…xny1y2…ym trên bảng chữ cái  .

Xâu xy được gọi là xâu ghép của hai xâu x và y. Như vậy, xâu ghép của hai xâu là một xâu được tạo ra bằng cách viết xâu thứ nhất, sau đó là xâu thứ hai (không có khoảng trống ở giữa).

Ví dụ: Xâu ghép của hai xâu w = abc và u = de trên bảng chữ cái La Tinh là xâu wu = abcde và w = w = w.

Ta ký hiệu: w0 = ; w1 = w; w2 = ww; ..., wi = wwi-1 với i > 0.

2) Phép đảo ngược xâu:

Cho xâu w = a1a2…an trên bảng chữ cái , phép đảo ngược xâu w là phép cho ta kết quả là một xâu trên bảng chữ cái , ký hiệu là wR và wR = anan-1…a2a1.

Xâu wR được gọi là xâu đảo ngược của xâu w. Như vậy, xâu đảo ngược của

xâu w là một xâu được tạo ra từ xâu w bằng cách viết w theo thứ tự ngược lại và hiển nhiên εR = ε.

1.1.5. Ngôn ngữ (language)

1) Khái niệm ngôn ngữ

Cho  là một bảng chữ cái, ký hiệu * là tập hợp tất cả các xâu trên  kể cả xâu rỗng, + là tập hợp tất cả các xâu trên  trừ xâu rỗng; như vậy, giữa * và + có mối liên hệ * = +  {} hay + = *- {}.

Ví dụ:

 = a, b, c;

*= aabcc, aaaaa, cab,…. là các xâu trên bảng chữ cái .

 = 0,1;

* = e,0,1,00,01,10,11,000… là tập các xâu trên .

+ = 0,1,00,01,10,11,000…

Ta quy ước xâu dạng aaaa…a gồm n kí tự a ký hiệu là an.

Cho bảng chữ cái , tập con bất kỳ của tập hợp * được gọi là ngôn ngữ (ngôn ngữ hình thức) trên bảng chữ cái .

Ví dụ:

Cho  = a; L = ai với a  và i  N thì L là ngôn ngữ trên bảng chữ cái .

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

Theo khái niệm ngôn ngữ thì ngôn ngữ L là một tập hợp. Ký hiệu |L| là số các xâu hay số phần tử của L; nếu |L| là một số hữu hạn thì nói rằng L là ngôn ngữ hữu hạn.

Từ các ngôn ngữ cho 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ữ.

Vì ngôn ngữ L là một tập hợp nên các phép toán hợp (union), giao (intersect), hiệu (difference) của lý thuyết tập hợp đều có thể áp dụng trên các ngôn ngữ của cùng một bảng chữ cái để thu được ngôn ngữ mới cũng trên bảng chữ cái đó. Tức là:

- Cho  là bảng chữ cái. L1, L2 là hai ngôn ngữ trên  thì: L1  L2 = x xL1 hoặc x L2;

L1  L2 = x xL1 và x L2;

L1 - L2 = x xL1 và x L2 cũng là các ngôn ngữ trên .

Ngoài ra, còn có một số phép toán thường gặp khác như:

- Phép lấy phần bù (complement):

Phần bù của một ngôn ngữ L trên bảng chữ cái  là một ngôn ngữ trên , ký hiệu là L và được xác định như sau:

- Phép nhân ghép (concatenation):

L = *- L

Tích ghép của hai ngôn ngữ L1và L2 trên bảng chữ cái Σ là một ngôn ngữ trên bảng chữ cái Σ và được xác định như sau:

L1L2 = {w1w2 | w1L1 và w2  L2 }

- Phép lặp (loop)

Cho L là ngôn ngữ trên bảng chữ cái .

Ký hiệu: L0 = , ở đây  ký hiệu cho từ rỗng, đó là từ không chứa ký hiệu nào của bảng chữ cái, hay là từ có độ dài bằng 0.

L1 = L;

L2 = L1L;

L3 = L2L, ...

Tổng quát: ký hiệu Li = Li-1L với i = 1, 2, …, n

- Phép lấy bao đóng (closure)

+ Bao đóng dương (positive)



L+ = L1  L2  L3 … = 

i1

Li với mọi n > 0; có thể coi L+ là tập tất cả

các xâu có độ dài hữu hạn và khác không.

+ Bao đóng kleene



L* = 

i1

Li với mọi n  0; như vậy, L* là tập tất cả các xâu có độ dài hữu hạn.

Chú ý: L+ = LL* = L*L = L* - {ε}.

L* = L+  {ε}.

Hiển nhiên, lặp, bao đóng của một ngôn ngữ L trên bảng chữ cái Σ là một ngôn ngữ trên bảng chữ cái Σ.

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

- L2 = {aa, aba, baa, baba};

- L3 = { aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa};

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

3) Biểu diễn ngôn ngữ

Ta biết rằng một ngôn ngữ L trên một bảng 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 thế nào có thể chỉ rò các xâu có thuộc vào L hay không ?. Đó chính là vấn đề biểu diễn ngôn ngữ. Để biểu diễn ngôn ngữ, ta có thể:

- Liệt kê:

+ Liệt kê hết: Đối với một ngôn ngữ hữu hạn, số lượng xâu của nó có ít, để biểu diễn nó, một cách đơn giản, ta chỉ cần liệt kê tất cả các xâu thuộc vào ngôn ngữ đó.

Ví dụ: L1 = {ε}

L2 = { a, ba, aaba, bbbbb }

+ Liệt kê không hết hết: Liệt kê một số xâu của ngôn ngữ và có ám chỉ quy luật để tìm các xâu khác.

Ví dụ: L1 = { ε, a, aa, aaa, aaaa, ... }

L 2 = { ε, ab, aabb, aaabbb, ... }

- Chỉ ra tính chất đặc trưng:

Trong trường hợp một ngôn ngữ là vô hạn hoặc không thể liệt kê được tất cả các xâu thuộc vào ngôn ngữ đó. Trong những trường hợp không phức tạp lắm, người ta thường phải tìm ra tính chất đặc trưng chung của các xâu và xác định các xâu bằng cách chỉ rò tính chất đặc trưng của các xâu đó. Tính chất đặc trưng này thường được mô tả thông qua một vị từ.

Ví dụ: L1 = { ai | i là một số nguyên tố }

L2 = { ai bi | i ≥ 0 }

L3 = { ai bj | i ≥ j ≥ 0 }

- 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 hoặc một automat. Văn phạm là cơ chế hay

công cụ cho phép sản sinh ra mọi xâu của một ngôn ngữ; trong khi đó automat lại là cơ chế hay công cụ cho phép đoán nhận một xâu 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à automat đều là cách biểu diễn khác nhau của ngôn ngữ.

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

- ε  L (1)

- Nếu w  L thì awb  L (2)

- Không còn xâu nào khác thuộc L (3)

Định nghĩa đệ quy trên cho ta một cách sản sinh ra các xâu thuộc ngôn ngữ L như sau: Do (1) nên ta có xâu đầu tiên trong L là ε. Xem đó là w thì theo (2) ta lại có được xâu thứ hai aεb hay ab. Áp dụng lặp đi lặp lại quy tắc (2) ta lại tìm được các xâu: aabb, rồi lại aaabbb, … Cứ như thế có thể phát sinh tất cả các xâu 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ỳ xâu nào trong ngôn ngữ.

Dễ dàng nhận thấy: L = {ai bi | i ≥ 0}.

Trong giáo trình này, các chương sau sẽ tập trung nghiên cứu hai công cụ dùng để biểu diễn ngôn ngữ, như đã nói ở trên, đó là văn phạm và automat, bằng cách ấn định các dạng khác nhau vào các công cụ để có thể đưa ra được nhiều loại văn phạm và automat khác nhau, từ đơn giản đến phức tạp và cũng sẽ nghiên cứu các ngôn ngữ được sinh bởi văn phạm hoặc được đoán nhận bởi automat và mối liên quan của chúng với nhau.

1.2. Văn phạm và ngôn ngữ

1.2.1. Văn phạm

Một công cụ để mô tả ngôn ngữ là văn phạm. Đây là công cụ có định nghĩa toán học chặt chẽ, được các nhà toán học nghiên cứu kỹ và trở thành một thành phần quan trọng, chính yếu của lý thuyết ngôn ngữ.

1) Định nghĩa

Văn phạm G là một hệ thống gồm bốn thành phần được xác định như sau: G = (N, T, P, S) trong đó:

+ N – Là một tập hữu hạn các ký hiệu không kết thúc (Nonterminal) hay tập các biến (variables).

+ T – Là tập hữu hạn các ký hiệu kết thúc hay ký hiệu cuối (Terminal) với N T = .

+ P – Là tập hữu hạn các quy tắc sinh hay còn được gọi là luật sinh. Nói một cách khác P là một ánh xạ từ tập (N  T) + sang tập (N  T)*

P: (N  T)+ → (N  T)*

α β

Giả sử α  (N  T)+, β (N  T)* và β là ảnh của α qua ánh xạ P, khi đó cặp (α, β) là một luật sinh và được ký hiệu là α  β.

+ SN - là ký hiệu chưa kết thúc đặc biệt dùng làm ký hiệu bắt đầu (start).

Ví dụ:

Văn phạm G = (N, T, P, S) trong đó:

- N = {S};

- T = {a, b};

- P = {S1  aS1b; S1 };

- S = S.

2) Quy ước

- Các chữ cái La Tinh viết hoa (A, B, C, ...) để chỉ các ký hiệu trong tập ký hiệu không kết thúc N; Chữ cái in hoa nằm ở vế trái của luật sinh đầu tiên là ký tự khởi đầu của văn phạm.

- Các chữ cái viết thường ở đầu bảng chữ cái La Tinh (a, b, c, ...) hoặc các chữ số để chỉ các ký hiệu kết thúc thuộc tập ký hiệu kết thúc T.

- Các chữ cái viết thường ở cuối bảng chữ cái La Tinh (x, y, z, w, ...) để chỉ xâu các ký hiệu kết thúc.

Nhận xét: Bằng quy ước này có thể suy ra được các ký hiệu không kết thúc, các ký hiệu kết thúc và ký hiệu bắt đầu của văn phạm một cách xác định và duy nhất bằng cách xem xét các luật sinh. Vì vậy, để biểu diễn một văn phạm, một cách đơn giản người ta chỉ cần liệt kê tập các luật sinh mà không cần chỉ rò đầy đủ các thành phần của của văn phạm.

1.2.2. Ngôn ngữ sinh bởi Văn phạm

1) Dẫn xuất

Nếu α → β là một luật sinh thì γ α δ  γ β δ được gọi là một dẫn xuất (trực tiếp), có nghĩa là áp dụng luật sinh α → β vào xâu γ α δ để sinh ra xâu γ β δ.

Nếu các xâu α , α , ...., α  (NT)* và α  α , α  α , ..., α  α thì ta nói

1 2 m 1 2 2 3 m-1 m

rằng: α được suy dẫn ra từ α thông qua dãy dẫn xuất α  α , α  α , ..., α  α

m 1 1 2 2 3 m-1 m

hay α dẫn xuất (gián tiếp) ra α .

1 m

Ký hiệu: - α i  α là dẫn xuất qua i bước;

1 m

- α * α là dẫn xuất qua không, một hoặc nhiều bước;

1 m

- α + α là dẫn xuất qua một hoặc nhiều bước.

1 m

2) Ngôn ngữ sinh bởi văn phạm

Ngôn ngữ sinh bởi văn phạm G = (N, T, P, S) là tập hợp các xâu w  T*

được dẫn xuất ra từ ký hiệu bắt đầu S của văn phạm bởi các luật sinh thuộc tập P và được ký hiệu là L(G). Như vậy:

L (G) = {w | w  T* và S * w} .

Ví dụ:

1. Cho G = (N, T, P, S) Với N = S, T = a

P = S  aaa, S  aaaS Khi đó L(G) = a3i iN

2. Cho văn phạm G = (N, T, P, S) với: N = S, T = 0,1;

P = S  0S1; S  01;

Ta có nhận xét mọi dãy dẫn xuất có thể có trong G phải có dạng: S  0S1  00S11  … 0i S1i

Từ đây suy ra L(G) =  0i1i  i  1

1.2.3. Văn phạm tương đương

Cho hai văn phạm G1 = (N1, T, P1, S1) và G2 = (N2, T, P2, S2), ta nói rằng G1 tương đương với G2 , ký hiệu là G1  G2 nếu L(G1) = L(G2).

Nói cách khác hai văn phạm được gọi là tương đương nếu chúng sinh ra cùng một ngôn ngữ.

Ví dụ:

Cho văn phạm G1 = (N1, T1, P1, S1) trong đó: N1 = {S1};

T1 = {a, b};

P1 = {S1  aS1b; S1 }.

Ta thấy ngay L(G1) = {anbn | n  0}. Và G2 = (N2, T2, P2, S2) trong đó:

N2 = {S2};T2 = {a, b};

P2 = {S2  aS2b; S2  ab; S2 }. Ta cũng thấy ngay L(G2) = {anbn | n  0}

Như vậy, G1 và G2 là hai văn phạm tương đương.

1.3. Phân loại văn phạm và ngôn ngữ

Ở trên đã xem xét văn phạm là một công cụ để sinh ra ngôn ngữ, tiếp theo ta sẽ xem xét các vấn đề liên quan đến câu hỏi có bao nhiêu loại ngôn ngữ ?. Quan hệ giữa chúng như thế nào ?. Liên quan đến các câu hỏi trên đã có nhiều nhà khoa học đưa ra cách phân loại khác nhau, song một cách phân loại được coi là tốt nhất, phù hợp với mục đích nghiên cứu là cách phân loại của nhà toán học Chomsky. Chomsky đưa ra cách phân loại ngôn ngữ dựa vào các quy tắc sinh và được sử dụng như là cách phân loại chủ yếu trong lý thuyết ngôn ngữ hình thức.

1.3.1. Văn phạm và ngôn ngữ loại 0

Văn phạm G được gọi là văn phạm loại 0 nếu các quy tắc sinh của nó không có bất kỳ một điều kiện ràng buộc nào. Văn phạm loại 0 còn có tên gọi là văn phạm ngữ cấu hay văn phạm không hạn chế (Unrestricted Grammar).

Ngôn ngữ sinh bởi văn phạm loại 0 được gọi là ngôn ngữ loại 0.