Trang chủ / Ngôn Ngữ Hình Thức

Biểu Diễn Automat Bằng Đồ Thị 27646


2) Nếu a thuộc T và α thuộc (NT)*=V, thì δ([aα], a) = {[α]}

Sau đó, có thể dễ dàng chứng minh quy nạp theo độ dài của dẫn xuất rằng δ([S], w) chứa [α] khi và chỉ khi có chuỗi dẫn xuất S * xA xyα với A → yα là một luật sinh trong P và xy = w, hay nếu α = S thì w = ε. Khi [ε] là trạng thái kết thúc duy nhất, M chấp nhận w khi và chỉ khi S * xA w. Nhưng vì mọi chuỗi dẫn xuất cho một chuỗi ký hiệu kết thúc qua ít nhất 1 bước, nên ta thấy rằng M chấp nhận w khi và chỉ khi G dẫn xuất ra w.

Bây giờ, giả sử G = (N, T, P, S) là một văn phạm tuyến tính trái. Đặt văn phạm G‟= (N, T, P‟, S) với P‟ chứa các luật sinh của P có vế phải đảo ngược, nghĩa là: P‟ = {A → αR | A → α P}.

Nếu đảo ngược xâu - vế phải các luật sinh trong một văn phạm tuyến tính trái

sẽ có văn phạm tuyến tính phải và ngược lại. Do đó, hiển nhiên sẽ có G‟ là một văn phạm tuyến tính phải và cũng dễ dàng để chỉ ra rằng L(G‟) R = L(G).

Như vậy, áp dụng các bước xây dựng NFA M‟ cho văn phạm G‟ và nếu đảo ngược các cạnh của NFA M‟ và chuyển đổi vai trò của các trạng thái bắt đầu và kết thúc thì sẽ có một NFA M đoán nhận ngôn ngữ L(G).

Để xây dựng từ vựng cho các ngôn ngữ lập trình bậc cao chỉ cần văn phạm chính quy trong trường hợp w bằng a T hoặc . Do đó, phần này chỉ đi sâu vào văn phạm chính quy trong trường hợp các luật sinh của nó có dạng A aB a (tuyến tính phải) hoặc A Ba a (tuyến tính trái) với A, B N; a T hoặc a = .

Theo cách chứng minh định lý trên, ta có giải thuật xây dựng Atomat hữu hạn khi biết văn phạm chính quy trong trường hợp đặc biệt này như sau.

b) Giải thuật xây dựng Atomat hữu hạn biết văn phạm chính quy

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

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

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

Output: FA M = <Q, , , q0, F>; L(M) = L(G)

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

Process:

1. Nếu G – văn phạm tuyến tính phải thì xây dựng Automat hữu hạn M có

- Q = N A; A là trạng thái mới bổ sung; A chưa có trong N;

- = T;

- q0 = S;

- F ={A};


- Hàm được xác định bằng cách:

(B, a) = {C B aC P};

(B, a) = {A B a P};

Trong đó: B, C N ; a hoặc a = .

+ (B, a) = trong các trường hợp còn lại.

2. Nếu G – văn phạm tuyến tính trái thì

- Xây dựng văn phạm tuyến tính phải G‟ với các luật sinh đảo ngược vế phải: P‟ = {A aB a sao cho A Ba a P};

- Xây dựng NFA M‟ tương ứng với văn phạm tuyến tính phải G‟;

- Xây dựng Automat hữu hạn M bằng cách đảo ngược các cạnh của NFA M‟ và chuyển đổi vai trò của các trạng thái bắt đầu và kết thúc.

Ví dụ:

1. Cho văn phạm tuyến tính phải G = (N, T, P, S). Trong đó: N = {S, A, B}; T = 0, 1; S = S;

P:

S 0A; B 1B;

S 1B; B 1;

A 0A; B 0;

A 0S; S 0; A 1B;

Áp dụng giải thuật trên có thể xây dựng Automat hữu hạn M = <Q, , q0, F)> đoán nhận các xâu của L(G) như sau:

Q = S, A, BC S, A, B, C; q0 = S; F = C

= 0, 1

Hàm chuyển (S, 0) = {A, C}; (S, 1) = B;

(A , 0) = {A, S}; (A, 1) = B;

(B, 1) = {B, C}; (B, 0) = C


Khi đó Automat có thể được biểu diễn bằng đồ thị như sau:

1

0

1

0

Start

S

0

A

1

B

1

C

0

0

Hình 2.26. Biểu diễn Automat bằng đồ thị

2. Cho văn phạm tuyến tính trái G = (N, T, P, S); Với N = S, A, B ; T = 0, 1 S = S;

P: S A1; S 1; S ; A B1; A 1; A B; B A0.

Áp dụng giải thuật trên, để có thể xây dựng Automat hữu hạn M đoán nhận các xâu của L(G) thực hiện:

- G‟ có các luật sinh P‟:

S 1A; S 1; S ; A 1B; A 1; A B; B 0A

- M‟ = <Q‟, ‟, ‟, q‟0, F‟> xác định như sau:

- Q‟ = N C = S, A, B, C

- ‟ 

- q‟0 = S

- F‟ = C

- ‟: ‟(S, 1) = A, C; ‟(S, ) = C;

‟(A, 1) = B, C‟(A, ) = B;

‟(B, 0) = A.

- M = <Q, , q0, F)>: Q = S, A, B, C



q0 = C

F = S

: (A, 1) = S; (C, 1) = S; (C, ) = S;

(B, 1) = A(C, 1) = A(B, ) = A;

(A, 0) = B.


Khi đó các Automat trên có thể được biểu diễn bằng đồ thị như sau:

0

Start

S

1

A

1

B

C

1,

1


M‟


0

S

1

A

1

B

C

Start

1,

1


M


Hình 2.27. Biểu diễn AutomatM và M’ bằng đồ thị

2) Định lý 2

Cho Automat hữu hạn M = <Q, , , q0, F>, khi đó tồn tại văn phạm chính quy G sao cho L(G) = L(M).

Chứng minh:

Trước hết, ta giả sử rằng trạng thái q0 không phải là trạng thái kết thúc. Tiếp theo đặt L = L(G) với văn phạm tuyến tính phải G = (N, T, P, S), trong đó:

- N = Q; T =  S = q0

- P chứa các luật sinh dạng p → aq nếu δ(p, a) = q và luật sinh dạng p → a nếu δ(p, a) là một trạng thái kết thúc. Rò ràng δ(p, w) = q khi và chỉ khi có dãy dẫn xuất p *wq. Nếu wa được chấp nhận bởi M, ta đặt δ(q0, w) = p, suy ra dẫn xuất q0 * wq. Tương tự, nếu δ(p, a) là trạng thái kết thúc, vì p → a là một luật sinh nên q0 *wa. Ngược lại, đặt q0 * x. Ta có x = wa và q0 * wq wa với mọi p và vì δ(q0, w) = p và δ(p, a) là trạng thái kết thúc nên x L(M). Hay nói cách khác : L(M)

= L(G) = L.


Bây giờ, xét q0 F, vì thế xâu rỗng ε thuộc L. Lưu ý rằng văn phạm G vừa xây dựng ở trên chỉ sinh ra ngôn ngữ L – {ε}. Ta có thể sửa đổi G bằng cách thêm vào một ký hiệu bắt đầu S mới với luật sinh S → q0 | ε. Văn phạm thu được vẫn có dạng tuyến tính phải và sinh ra ngôn ngữ L.

Để xây dựng văn phạm tuyến tính trái cho L, bắt đầu với một NFA cho LR và sau đó đảo ngược xâu vế phải cho tất cả mọi luật sinh của văn phạm tuyến tính phải vừa xây dựng sẽ thu được văn phạm tuyến tính trái cho L.

b) Giải thuật xây dựng văn phạm chính quy biết Atomat hữu hạn

Input: FA M = <Q, , , q0, F>

Output: RG G = (N, T, P, S); L(M) = L(G)

Process:

- N = Q ;

- T = 

- S = q0 ;

1. Nếu xây dựng G = (N, T, P, S) – văn phạm tuyến tính phải thì P được xác định như sau:

+ B aC P nếu (B, a) = C và C F;

+ B aC a P nếu (B, a) = C và C F; Với B, C Q; a T {}.

2. Nếu xây dựng G = (N, T, P, S) – văn phạm tuyến tính trái thì

- Nếu NFA M có nhiều trạng thái kết thúc thì thêm vào một trạng thái mới làm trạng thái kết thúc; bỏ các trạng kết thúc cũ của M và nối chúng với trạng thái kết thúc mới bằng các cung có hướng mang nhãn .

- Xây dựng automat hữu hạn M‟ đảo ngược của M bằng cách đảo ngược các cạnh của NFA M và chuyển đổi vai trò của các trạng thái bắt đầu và kết thúc.

- Xây dựng văn phạm tuyến tính phải G‟ tương ứng với FA M‟.

- Xây dựng văn phạm tuyến tính trái G mà tập luật sinh có được bằng cách đảo ngược các xâu - vế phải của các luật sinh trong G‟.

Ví dụ:


Cho Automat M = <Q, , , q0, F>; Trong đó: Q = {q0, q1, q2};

= {0, 1};

q0 = q0; F = {q2};

: (q0, 1) = {q0, q1};

(q1, 1) = {q2};

(q2, 0) = {q2}.

- Áp dụng giải thuật trên, xây dựng văn phạm tuyến tính phải G = (N, T, P, S) tương ứng với M như sau:

N = {q0, q1, q2}; T = {0, 1}; S = q0 ; P:

q0 1q0 1q1 ; q1 1q2 1;

q2 0q2 0.

Đặt q0 = S ; q1 = A; q2 = B ta có:

P: S 1S 1A; A 1B 1; B 0B 0.

- Áp dụng giải thuật trên, xây dựng văn phạm tuyến tính trái G = (N, T, P, S) tương ứng với M như sau:

+ Từ FA M có FA M‟ = <Q, , ‟, q‟0, F‟> đảo ngược:

q‟0 = q2 ; F‟ = {q0};

‟: (q0, 1) = {q0};(q1, 1) = {q0};

(q2, 1) = {q1};

(q2, 0) = {q2}.

+ Văn phạm tuyến tính phải tương ứng với M‟:

N‟ = {q0, q1, q2}; T‟ = {0, 1}; S‟ = q2 ;


P‟: q2 0q2 ;

q2 1q1; q1 1q0 1; q0 1q0 1.

+ Văn phạm tuyến tính trái tương ứng với:

N = {q0, q1, q2}; T = {0, 1}; S = q2 ;

P: q2 q20; q2 q11; q1 q01 1;

q0 q0 11. Đặt q2 = S ; q1 = A; q0 = B ta có:

P: S S0 A1; A B1 1; B B1 1.

2.3.3. Tính chất của ngôn ngữ chính quy

Một số tính chất chung của ngôn ngữ đã đề cập ở phần trên. Phần này ta sẽ nêu các tính chất của ngôn ngữ chính quy (ngôn ngữ loại 3), trong đó có một số tính chất có thể suy từ các tính chất chung của ngôn ngữ.

1) Tính chất 1: Ngôn ngữ loại 3 kín với phép hợp

Chứng minh:

Giả sử L1 và L2 là ngôn ngữ loại 3 tương ứng sinh bởi G1 = (N1, T1, P1, S1) và G2 = (N2, T2, P2, S2 ). Tức là L1 = L(G1); L2 = L(G2).

Ta xây dựng văn phạm G3 như sau: G = (N, T, P, S); trong đó:

N = N1N2S và S chưa có trong N1, N2, T1, T2; T = T1 T2;

P = P1 P2 S S1 P1 hoặc S2  P2

Dễ dàng thấy rằng trong trường hợp L(G1) hoặc L(G2) chứa từ rỗng ta thêm vào G quy tắc S 


2) Tính chất 2: Ngôn ngữ loại 3 kín với phép lấy phần bù

Chứng minh:

Giả sử A = <Q, , , q0, F> đoán nhận tập T(A) *, giả sử 1 là tập con của

1

Ta xây dựng Automat A‟ = <Q‟, 1, ‟, q0, F‟> đoán nhận tập *-T(A) như sau:

Q‟ = Q d; F‟ = Q-F d;

‟ xác định như sau:

‟(q, a) = (q, a) nếu q Q; a

‟(q, a) = d nếu q Q; a 1 - 

‟(d, a) = d nếu a 1.

Với cách xây dựng A‟ như trên rò ràng A‟ là mở rộng của A trên tập 1 bằng cách thêm vào trạng thái d và có thể kiểm tra được bằng A‟ đoán nhận 1*-T(A).

3) Tính chất 3: Tất cả các xâu hữu hạn đều là ngôn ngữ loại 3.

Chứng minh:

Xét xâu hữu hạn x = a1a2…an. Ta xây dựng Automat A gồm n + 2 trạng thái q0, q1, q2,… qn và p, trong đó q0 là trạng thái đầu, qn là trạng thái kết thúc. A hoạt động như sau khi nó nhận ra ký tự của xâu x, nó sẽ dịch chuyển đến trạng thái có chỉ số cao hơn. Nếu A không nhận ra ký tự của xâu x nó sẽ chuyển sang trạng thái p là trạng thái “bẫy”.

Cụ thể hàm chuyển của A như sau:

(qi-1, ai) = qi với i = 1, 2, …, n;

(qi-1, a) = p; với a ai và i = 1, 2, …, n;

(qn, a) = (p, a) = p với mọi a .

Dễ dàng kiểm tra được rằng A đoán nhận xâu x.

Trong trường hợp x là xâu rỗng ta có thể xây dựng A = <Q, , , q0, F> trong đó

Q = q0, p;F = q0; (q0, ) = q0; (q0, a) = (p, a) = p với a

4) Tính chất 4: Lớp các ngôn ngữ loại 3 đóng với phép nhân ghép.

Chứng minh:

Giả sử M1 = <Q1, 1, 1, q1, F1> đoán nhận ngôn ngữ L1 = T(M1);

..... Xem trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 16/07/2022