Trang chủ / Chương Trình Dịch

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


Begin

Q‟: = {q0};

‟:=

Hình 2.14 là sơ đồ khối của giải thuật xác định Q‟ và ‟. Giả sử ta đánh số các ký hiệu của ‟ là a1, a2,..., an


T Q‟ chưa đánh dấu

s

End

đ

s

i n


đ

B:= (T, ai)

Q‟:= Q‟ {B};

‟ := ‟ { ‟(T, ai) = B }

i := i+1

Đánh dấu T

i := 1

Hình 2.14. Sơ đồ giải thuật

Ví dụ 2.21:

a) Cho Automat hữu hạn NFA M = < Q, , , q0, F > có đồ thị chuyển là hình

Start

0

a

1

a

2

b

3

b

b

a

2.15. Hãy xây dựng Automat hữu hạn đơn định D đoán nhận cùng ngôn ngữ với M. a


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


Ta có thể nhận thấy M đoán nhận ngôn ngữ N(M) = b*(a| b)a+(a| b) Áp dụng giải thuật, ta có:

D = ‟, ‟, q‟0, F‟>. Trong đó:

- ‟ = {a, b};

- q‟0 = {0} = A; Q‟ = {A};

- Xét A:

+ (A, a) = ({0}, a) = (0, a) = {1} = B

Q‟ = {A, B}; ‟ = {‟(A, a) = B}

+ (A, b) = ({0}, b)) = (0, b) = {0, 1} = C

Q‟ = {A, B, C}; ‟ = {‟(A, a) = B; ‟(A, b) = C}

- Xét B:

+ (B, a) = (1, a) = {1} = B

Q‟ = {A, B, C}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B}

+ (B, b)) = (1, b) =

Q‟ = {A, B, C};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B}

- Xét C:

+ (C, a)) = ({0, 1}, a) = (0, a) (1, a) = {1, 2} = D

Q‟ = {A, B, C, D};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D}

+ (C, b)) = ({0, 1}, b) = (0, b) (1, b) = {0, 1} = C

Q‟ = {A, B, C, D};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D;

‟(C, b) = C}

- Xét D:

+ (D, a)) = ({1, 2}, a) = (1, a) (2, a) = {1, 2} {3}= {1, 2, 3}= E

Q‟ = {A, B, C, D, E};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D;

‟(C, b) = C; ‟(D, a) = E}


+ (D, b)) = ({1, 2}, b) = (1, b) (2, b) = {3} = F

Q‟ = {A, B, C, D, E, F};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D;

‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F}

- Xét E:

+ (E, a)) = ({1, 2, 3}, a) = (1, a) (2, a) (3, a) = {1, 2, 3}= E

Q‟ = {A, B, C, D, E, F};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D;

‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E}

+ (E, b)) = ({1, 2, 3}, b) = (1, b) (2, b) (3, b) = {3}= F

Q‟ = {A, B, C, D, E, F};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D;

‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E;‟(E, b) = F}

- Xét F:

(F, a)) = ({3}, a) = (3, a) =

Q‟ = {A, B, C, D, E, F};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D;

‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E;‟(E, b) = F}

(F, b)) = ({3}, b) = (3, b) =

Q‟ = {A, B, C, D, E, F};

‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D;

‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E;‟(E, b) = F}

- F‟ = {E, F}.

Vậy D = ‟, ‟, q‟0, F‟>. Trong đó:

Q‟ = {A, B, C, D, E, F} ;

‟ = {a, b}; q‟0 = A;

‟:{‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C;

‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E; ‟(E, b) = F}


F‟ = {E, F}.

Đồ thị chuyển của automat D

Start

A

a

B

a

C

a

D

a

E

b

F

b

b

a b a


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

Ta có thể nhận thấy D đoán nhận ngôn ngữ L(M) = b*a+(b | ) Ta có thể tóm tắt kết quả của việc thực hiện giải thuật trên như sau:

- q‟0 = {q0} = A;

- ‟ = {a, b};

- Xác định Q‟ và ‟


Bước

Đánh dấu T

ai

B = (T, ai)

Bổ sung vào Q‟

Bổ sung vào ‟

Kt



{0} = A

A


1

A

a

{1} = B

B

‟(A, a) = B



b

{0, 1}= C

C

‟(A, b) = C

2

B

a

{1} = B


‟(B, a) = B



b



3

C

a

{1, 2}= D

D

‟(C, a) = D



b

{0, 1}= C


‟(C, b) = C

4

D

a

{1, 2, 3}= E

E

‟(D, a) = E



b

{3} = F

F

‟(D, b) = F

5

E

a

{1, 2, 3}= E


‟(E, a) = E



b

{3}= F


‟(E, b) = F

6

F

a





b



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

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

Chương trình dịch - 8

Bảng 2.9. Mô phỏng giải thuật

- Xác định F‟ = {B, C}.


2.6. Giải thuật Thomson

Với mục đích sử dụng Automat hữu hạn để phân tích từ vựng. Thomson đã đưa ra giải thuật giải quyết bài toán sau: Cho trước một biểu thức chính quy. Hãy xây dựng Automat đoán nhận ngôn ngữ được biểu diễn bởi biểu thức chính quy đó. Tư tưởng của giải thuật dựa vào ý tưởng, mọi biểu thức chính quy đều có thể phân tích thành các biểu thức chính quy đơn giản hơn. Từ đó đi xây dựng các Automat đơn giản đoán nhận các biểu thức chính quy đơn giản. Sau đó tổng hợp nó để được Automat cần xây dựng.

1) Phương pháp xây dựng các automat đoán nhận các biểu thức chính quy đơn giản

a) Xây dựng Automat đoán nhận từ rỗng . Hình 2.17 là Automat đoán nhận từ rỗng với i là trạng thái bắt đầu, f là trạng thái kết thúc.


Start

i

f

Hình 2.17. Automat đoán nhận biểu thức r=

b) Xây dựng Automat đoán nhận ký tự a.


Start

i

a

f

Hình 2.18. Automat đoán nhận biểu thức r = a

Hình 2.18 là sơ đồ biểu diễn Automat đoán nhận a, với i là trạng thái bắt đầu, f là trạng thái kết thúc.

2) Phương pháp xây dựng các automat tổng hợp từ các automat

a) Giả sử s và t là hai biểu thức chính quy và N(s), N(t) là hai Automat đoán nhận s và t tương ứng khi đó Automat đoán nhận biểu thức chính quy s + t có dạng như hình 2.19.


N(s)

Start

i

f

N(t)

Hình 2.19. Automat đoán nhận biểu thức r = s+t


Ở đây i, f là các trạng thái mới chưa có trong N(s), N(t), từ trạng thái bắt đầu i Automat nhìn thấy từ rỗng; nó có thể chuyển sang trạng thái bắt đầu của N(r) hoặc trạng thái bắt đầu của N(t). Ngược lại từ trạng thái cuối của N(s) hoặc N(t) nó có thể chuyển sang trạng thái kết thúc f khi gặp từ rỗng.

b) Xây dựng Automat đoán nhận biểu thức chính quy st. Giả sử N(s), N(t) là hai Automat đoán nhận svà t tương ứng khi đó Automat đoán nhận biểu thức chính quy st có dạng như hình 2.20.


Start

i

N(s)

N(t)

f


Hình 2.20. Automat đoán nhận biểu thức r=st

Ở đây i là trạng thái mới chưa có trong N(s) và N(t), khi gặp từ rỗng Automat chuyển đến trạng thái đầu của N(s), trạng thái kết thúc của N(s) và trạng thái bắt đầu của N(t) được kết hợp thành một trạng thái, trạng thái kết thúc của N(t) trở thành trạng thái kết thúc của Automat hợp thành.

c) Giả sử s là biểu thức chính quy, và N(s) là Automat đoán nhận nó, ta xây dựng Automat đoán nhận s* và s+. Hình 2.21a mô tả Automat N(s*), Hình 2.21 b

mô tả Automat N(s+)

Start

i

N(s)

f


Hình 2.21a. Automat đoán nhận biểu thức r = s*

Start

i

N(s)

f

Hình 2.21b. Automat đoán nhận biểu thức r = s+

Ở đây i, f là trạng thái mới tương ứng là trạng thái bắt đầu và trạng thái cuối cùng của Automat.


3) Giải thuật Thomson

Input: r – biểu thức chính quy; Output: NFA M ; N(M) = N(r). Process:

Bước 1: Phân tích r thành các biểu thức chính quy đơn giản

- Tìm trong biểu thức chính quy phép toán có thứ tự ưu tiên thấp nhất

- Nếu có thì phân tích biểu thức chính quy thành các toán hạng theo phép toán đó. Mỗi toán hàng – một biểu thức chính quy đơn giản hơn.

- Quay lại bước 1 cho đến khi đã phân tích tất cả các biểu thức chính quy thánh các biểu thức chính quy đơn giản dạng r = a.

Bước 2: Xây dựng

- Xây dựng các automat đơn giản đoán nhận các biểu thức chính quy đơn giản.

- Xây dựng các automat tổng hợp theo thứ tự ngược lại cho đến khi xây dựng automat tổng hợp đoán nhận biểu thức chính quy r.

Nhận xét:

- Với biểu thức chính quy r, Automat N(r) đoán nhận nó sẽ có số trạng thái nhiều nhất không vượt quá hai lần số ký tự có trong r và số phép toán có trong nó. Điều nhận xét này có được là do trong giải thuật Thomson với mỗi ký hiệu hoặc phép toán trong r ta thêm vào không quá hai trạng thái.

- Mỗi Automat N(r) xây dựng theo giải thuật Thomson chỉ có một trạng thái đầu và một trạng thái kết thúc, và trạng thái kết thúc không bao giờ chuyển sang một trạng thái nào khác.

- Mỗi trạng thái của Automat N(r) chỉ có một trạng thái chuyển đi theo ký hiệu của tập và tối đa hai trạng thái chuyển đi theo ký hiệu rỗng , vì vậy nói chung Automat xây dựng theo giải thuật Thomson là Automat không đơn định.

- Do mỗi lần xây dựng một Automat mới ta thêm vào trạng thái bắt đầu và kết thúc mới, cho nên Automat xây dựng theo giải thuật Thomson không có hai trạng thái trùng nhau.


Ví dụ 2.22:

Cho r = (a b)*abb. Hãy xây dựng NFA đoán nhận biểu thức chính quy r theo giải thuật Thomson.

Bước 1: Phân tích r = (a + b)*abb

- r = r1r2;

r1 = (a + b)*ab; r2 = b;

- r1 = r3r4;

r3 = (a + b)*a; r4 = b;

- r3 = r5r6;

r5 = (a + b)*; r6 = a;

- r5 = (r7)*; r7 = a + b;

- r7 = r8r9;

R8 = a ; r9 = b;

Bước 2: Xây dựng

- Xây dựng Automat đoán nhận r8= a; r9 = b


Start

2

a

3


Start

4

b

5

Hình 2.22. Các automat đoán nhận a, b


- Xây dựng Automat đoán nhận r7 = r8 + r9


2

a

3

Start

1

6

4

b

5

Hình 2.23. Automat đoán nhận r7 = a+b

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

Ngày đăng: 28/06/2022