Tính Chất 5 (Tính Đệ Quy Của Ngôn Ngữ)

1.3.2. Văn phạm và ngôn ngữ loại 1

Văn phạm G được gọi là văn phạm loại 1 nếu các quy tắc sinh của nó có dạng:  , với điều kiện (NT)+ và 

Văn phạm loại 1 còn được gọi là văn phạm cảm ngữ cảnh (Context Sensitive Grammar - CSG).

Ngôn ngữ sinh bởi văn phạm loại 1 được gọi là ngôn ngữ loại 1 và còn được gọi là ngôn ngữ cảm ngữ cảnh (CSL).

1.3.3. Văn phạm và ngôn ngữ loại 2

Văn phạm G được gọi là văn phạm loại 2 nếu các quy tắc sinh của nó có dạng: ; với N  (NT)*.

Văn phạm loại 2 còn được gọi là văn phạm phi ngữ cảnh (Context free Grammar - CFG).

Ngôn ngữ sinh bởi văn phạm loại 2 được gọi là ngôn ngữ loại 2 và còn được gọi là ngôn ngữ phi ngữ cảnh (CFL).

1.3.4. Văn phạm và ngôn ngữ loại 3

Văn phạm G được gọi là văn phạm loại 3 nếu mọi quy tắc sinh của nó có một trong hai dạng:

1. A  Bw hoặc A  w (văn phạm tuyến tính trái);

2. A  wB hoặc A  w (văn phạm tuyến tính phải). Trong đó: A, BN và wT*.

Văn phạm loại 3 còn được gọi là văn phạm chính quy (Regular Grammar - RG).

Ngôn ngữ sinh bởi văn phạm loại 3 được gọi là ngôn ngữ loại 3 và còn được gọi là ngôn ngữ chính quy (RL).

Chú ý:

Từ cách phân loại trên ta có nhận xét: Văn phạm loại 3 cũng là văn phạm loại 2; văn phạm loại 2 cũng là văn phạm loại 1; văn phạm loại 1 cũng là văn phạm loại 0. Tức là: G3  G2  G1  G0.

Từ đây suy ra nhận xét trên cũng đúng với các loại ngôn ngữ. Tức là:

L3  L2  L1  L0.

1.3.5. Ví dụ

1) Xét văn phạm G = (N, T, P, S): a) - N = {S, A};

- T = {a, b};

- S = S;

- P = {S → aS; S → aA; A → bA; A → b}

Đây là văn phạm loại 3 (vì tập luật sinh có dạng tuyến tính phải).

Chẳng hạn, một dẫn xuất từ S có dạng:

3 4

S  aS  aaS  aaaA  aaabA  aaabbA  aaabbbA  aaabbbb = a b

m n

Hay văn phạm sinh ra ngôn ngữ L(G) = {a b | m, n ≥ 1}

b) - N = {S};

- T = {a, b};

- S = S;

- P: S → abS  a

là văn phạm tuyến tính phải. c) - N = {S, A, B};

- T = {a, b};

- S = S;

- P: S → Aab; A → Aab B; B → a 

là văn phạm tuyến tính trái.

2) Xét văn phạm G = (N, T, P, S): N = {S};

T = {a, b};

P = { S → aSb; S → ab } Đây là văn phạm loại 2 (CFG).

Chẳng hạn, một dẫn xuất từ S có dạng:

4 4

S  aSb  aaSbb  aaaSbbb  aaaabbbb = a b

n n

Hay văn phạm sinh ra ngôn ngữ L(G ) = {a b

| n ≥ 1}

3) Xét văn phạm G = (N, T, P, S): N = {S, B, C};

T = {a, b, c};

P = { S → aSBC; S → aBC; CB → BC; aB →ab; bB → bb; bC → bc; cC → cc}. Đây là văn phạm loại 1 (CSG).

Chẳng hạn, một dẫn xuất từ S có dạng:

S  aSBC  aaBCBC  aabCBC  aabBCC  aabbCC  aabbcC

2 2 2

 aabbcc = a b c

n n n

Hay văn phạm sinh ra ngôn ngữ L(G ) = {a b c

| n > 0}.

4) Xét văn phạm G = (N, T, P, S): N = {S, A};

T = {a, b, c};

S = S;

P: SA → a; S → bcA; acS → cA. Đây là văn phạm loại 0.

1.4. Một số tính chất của ngôn ngữ

Bản chất của ngôn ngữ là tập hợp vì vậy ngôn ngữ mang đầy đủ các tính chất của tập hợp, mặt khác ngôn ngữ lại được sinh ra bởi văn phạm vì vậy cần phải xem xét ngoài các tính chất của tập hợp ngôn ngữ còn có thêm những tính chất gì ?. Phần này sẽ trình bày một số tính chất của ngôn ngữ do văn phạm sinh ra.

1.4.1. Tính chất 1

Loại của ngôn ngữ đóng với phép hợp.

Nói cách khác, tính chất 1 khẳng định rằng hợp của 2 ngôn ngữ cùng loại là ngôn ngữ cùng loại.

Giả sử cho 2 văn phạm cùng loại G1 = (N1, T, P1, S1), G2 = (N2, T, P2, S2), văn phạm G1, G2 tương ứng sinh ra ngôn ngữ L1, L2. Giả sử L = L1  L2 ta cần chứng minh: L là ngôn ngữ được sinh ra bởi văn phạm G cùng loại với văn phạm G1, G2. Điều đáng lưu ý ở đây là hai văn phạm phải có cùng bảng chữ cái T thì việc xem xét mới có nghĩa.

Ta xây dựng văn phạm G = (N, T, P, S) thoả mãn 2 điều kiện:

- G cùng loại với G1, G2;

- G sinh ra L mà L = L1  L2.

Muốn thế, ta lấy N = N1 N2 S (S không thuộc N1, N2); P = P1 P2 SS1, SS2.

Với cách xây dựng G như trên rò ràng G cùng loại với G1, G2. Bây giờ, ta

cần chứng tỏ: L = L(G) = L1 L2.

Giả sử wL, theo định nghĩa S * w trong G, từ cách xây dựng P, bước đầu tiên trong G chỉ có thể:

S  S1* w hoặc S  S2 * w; nhưng từ S1 * w hoặc S2 * w ta suy ra w  L1L2. Ngược lại nếu w  L1  L2, khi đó w  L1 hoặc w L2.

Theo định nghĩa suy ra S1 * w hoặc S2 * w. Nếu w  L1 có nghĩa là

S1 * w . Suy ra S  S1 * w ; tức là S * w hay w  L, còn nếu w L2 có nghĩa là S2 * w. Suy ra S  S2 * w suy ra S * w hay w  L.

1.4.2 Tính chất 2

Loại của ngôn ngữ đóng với phép lặp.

Tính chất 2 khẳng định rằng phép lặp của một ngôn ngữ là một ngôn ngữ cùng loại. Nghĩa là nếu M = L L…L = Li thì M là ngôn ngữ cùng loại với L. Ta có thể kiểm tra tính đúng đắn của các tính chất trên.

1.4.3. Tính chất 3

Cho G = (N, T, P, S) không phải là văn phạm loại 0, có ký hiệu ban đầu S ở vế phải của quy tắc sinh khi đó tồn tại văn phạm G‟ cùng loại và tương đương với G không có ký hiệu bắt đầu ở vế phải của quy tắc sinh.

Chứng minh:

Giả sử cho G = (N, T, P, S) là văn phạm loại 1, hoặc loại 2, hoặc loại 3, ta xây dựng G‟= (N‟, T, P‟, S‟) như sau:

N‟= N S‟; ở đây S‟ là ký hiệu mới chưa có trong N và T. P‟ = P S‟ nếu S  P,  (NT)+

Nói cách khác P‟ gồm tất cả các quy tắc sinh của G có bổ sung thêm các quy tắc sinh dạng S‟  nếu trong P có quy tắc sinh dạng S .

Với cách xây dựng trên rò ràng trong G‟ không có quy tắc nào mà ký hiệu bắt đầu S‟ xuất hiện ở vế phải. Bây giờ, ta chỉ cần chứng minh G và G‟ là tương đương, nghĩa là L(G) = L(G‟).

Giả sử w  L(G) khi đó theo định nghĩa ta có dẫn xuất S * w, tách bước đầu tiên của dẫn xuất này ta có S * w, với  (NT)+. Theo cách xây dựng G‟ vì trong G có quy tắc S  nên trong G‟ có quy tắc S‟. Khi đó, dẫn xuất S‟* w là ở trong G‟ vì dẫn xuất * w trong G cũng là dẫn xuấu trong G‟.

Suy ra w  L(G‟) hay L(G)  L(G‟).

Ngược lại giả sử w L(G‟) khi đó theo định nghĩa ta có S‟ * w. Lập luận tương tự như trên ta có L(G)  L(G‟). Suy ra L(G) = L(G‟).

Chú ý:

Tính chất 3 cho phép ta coi các văn phạm loại 1, 2, 3 không có ký hiệu bắt đầu ở vế phải của các quy tắc sinh. Do đó nếu từ rỗng  L(G) thì trong P ắt phải có quy tắc S .

1.4.4. Tính chất 4

Cho G = (N, T, P, S) không phải là văn phạm loại 0, khi đó L(G) hoặc L(G)  là ngôn ngữ cùng loại L(G).

Chứng minh:

Tính chất 4 dễ dàng được chứng minh nhờ tính chất 3 vì nếu văn phạm không phải là văn phạm loại 0 sinh ra từ rỗng thì tập các quy tắc sinh P có chứa quy tắc S . Vì vậy, tập ngôn ngữ L(G)- hoặc L(G)  tương ứng với việc loại bỏ khỏi hay bổ sung thêm vào P quy tắc sinh S  và với điều này rò ràng không làm thay đổi loại của ngôn ngữ.

1.4.5. Tính chất 5 (Tính đệ quy của ngôn ngữ)

Ta nói rằng văn phạm G là đệ quy nếu tồn tại thuật toán xác định một từ w cho trước có thuộc L(G) hay không? Trước khi nói đến tính đệ quy của ngôn ngữ ta có vài nhận xét sau:

- Giả sử G = (N, T, P, S) là văn phạm cảm ngữ cảnh, xâu rỗng  L(G) khi và chỉ khi tập P có quy tắc S . Như vậy, ta cần phải kiểm tra quy tắc S  có trong P hay không? Bằng cách loại quy tắc S  khỏi P, ta có văn phạm cảm ngữ cảnh mới:

G‟ = (N, T, P‟, S)

Văn phạm G‟ sinh ra L(G) , mỗi dẫn xuất trong G‟ thoả mãn điều kiện của văn phạm cảm ngữ cảnh. Nghĩa là trong mọi quy tắc sinh của G‟ có độ dài vế phải lớn hơn hoặc bằng vế trái.

Giả sử V = NT, V = n và w là xâu khác xâu rỗng thuộc L(G‟). Ta suy ra S * w. Giả sử dẫn xuất có dạng:

S 12 … m (a) Ở đây m= w. Từ nhận xét trên ta suy ra:

12 … m

Giả sử rằng tồn tại i sao cho các xâu i, i+j trong dãy dẫn xuất trên có độ dài như nhau và bằng p. Giả sử rằng j > np khi đó suy ra trong dãy dẫn xuất (a) có ít nhất hai xâu giống nhau, do đó suy ra trong V* chỉ có nhiều nhất là np xâu có độ dài p trong trường hợp ngược lại ta có thể bỏ đi ít nhất một bước trong dãy dẫn xuất trên. Giả sử r = s với r < s khi đó dẫn xuất (a) có thể viết lại ngắn hơn là:

S i … r s+1 … m= w.

Về mặt trực quan cho phép ta nhận xét nếu có một dẫn xuất của w thì nó sẽ có dẫn xuất không quá dài. Nhận xét này là cơ sở cho định lý sau:

Định lý: Cho G = (N, T, P, S) là văn phạm cảm ngữ cảnh khi đó G là văn phạm đệ quy.

Chứng minh:

Từ nhận xét ở trên, giả sử L(G) không chứa từ rỗng, khi đó ta có quyền giả thiết P không chứa quy tắc S  và w thuộc L(G), wT+ và w = n. Ta cần chỉ ra thuật toán xác định w có thuộc L(G) hay không?

Ta định nghĩa tập Tm như sau:

Tm = V+;  n ; S * có không quá m bước Rò ràng T0 =S;

Ta cũng dễ dàng thấy rằng có thể tìm Tm qua Tm-1 Tm = Tm-1;  Tm-1;  n (b)

Nếu S * và  n thì  phải thuộc vào một Tm nào đó, trái lại nếu không dẫn xuất được ra  hoặc > n thì  sẽ không thuộc bất kỳ Tm nào.

Từ cách xây dựng Tm ở trên suy ra Tm là dãy không giảm Tm-1  Tm với mọi m 1; hơn nữa, dãy này bị chặn nên tồn tại m mà Tm= Tm-1 = T‟. Nếu w không thuộc Tm khi đó w không thuộc L(G) và đương nhiên nếu w thuộc Tm thì S * w.

Giả sử V = NT và V= q, khi đó trong V+ số xâu có độ dài nhỏ hơn hoặc

bằng n là s = q + q2 + q3+……+ qn. Ta có s < (1+q)n+1, rò ràng số từ này là hữu hạn trong T‟. Vì vậy, ta có thể so w với các từ có trong T‟. Nghĩa là tồn tại thuật toán để xác định xem w có thuộc L(G) hay không?.

Ví dụ:

Cho

G = (N, T, P, S):

N= S, B, C;

T= a, b, c;

S  aSBC; S  aBC;

CB  BC; aB  ab;

BB  bb; bC bc;

cC cc;

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

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

Xét từ w = abac trong L(G); theo cách xây dựng Tm trong định lý trên ta có: T0 = S;

T1 = S, aSBC, aBC;

T2 = S, aSBC, aBC, abc; T3 = S, aSBC, aBC, abc; T3 = T2 = T‟

Vì w = abac không thuộc T‟ nên w không thuộc L(G).

1.5. Automat

1.5.1. Mô tả automat

Ngoài văn phạm, người ta còn sử dụng một phương tiện khác để biểu diễn ngôn ngữ; đó là automat. Automat được hiểu là một “máy” trừu tượng có cơ cấu và hoạt động rất đơn giản nhưng có khả năng đoán nhận ngôn ngữ. Với một xâu bất kỳ, sau một số bước làm việc, automat sẽ cho câu trả lời xâu đó có thuộc ngôn ngữ hay không. Để có được quá trình tự động như vậy, người ta thường phải lập trình sẵn cho nó một “lộ trình” thực hiện và các máy chỉ cần hoạt động theo đúng lộ trình này. Một trong số những máy tự động này điển hình mạnh nhất có thể nói chính là

máy tính số ngày nay. Tuy hoạt động theo kiểu “máy”, song thực chất mỗi bước làm việc của automat là một sự thay thế ký hiệu, nghĩa là một bước dẫn xuất như đã nói ở trên. Nói chung, một mô hình automat thường bao gồm những thành phần chủ yếu như sau:

…

Băng vào

Đầu đọc

Bộ điều khiển

Hình 1. Mô hình chung cho một automat

Xâu vào cần xác định sẽ được lưu trữ trên băng vào (input). Tại mỗi thời điểm, ứng với trạng thái hiện thời, máy đọc một ký tự trên băng vào (input), có thể kết hợp với việc xem xét ký hiệu tương ứng trong bộ nhớ, bộ điều khiển của automat sẽ quyết định bước chuyển đến trạng thái tiếp theo.

Các loại automat tương ứng với một số lớp văn phạm sẽ được giới thiệu lần lượt trong các chương tiếp theo.

1.5.2. Phân loại automat

Dựa vào sự hoạt động của automat, có thể chia automat thành hai loại automat đơn định và automat không đơn định.

Automat đơn định (Deterministic Automata): Là một automat mà tại mỗi bước di chuyển, bộ điều khiển chỉ có duy nhất một khả năng lựa chọn trạng thái được chuyển đến tiếp theo khi đọc vào một ký tự trên băng vào. Sự duy nhất này thể hiện tính đơn định, nghĩa là hàm chuyển của automat dạng này luôn là đơn trị.

Automat không đơn định (Non - deterministic Automata): Là một automat mà tại mỗi bước di chuyển, bộ điều khiển có một vài khả năng để chọn lựa trạng thái được chuyển đến tiếp theo khi đọc vào một ký tự trên băng vào. Sự chọn lựa này thể hiện tính không đơn định, nghĩa là hàm chuyển của automat dạng này là đa trị.