Mô Tả Quá Trình Đoán Nhận Xâu

5

{2, 3}	b
6	{2, 3}	b
7	{2, 3}	$

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

• Nhắc Lại Một Số Kiến Thức Về Văn Phạm – Ngôn Ngữ - Automat
• Thẻ Từ, Mẫu Từ Vựng Và Trị Từ Vựng (Từ Vị)
• Kỹ Thuật Sử Dụng Automat Để Phân Tích Từ Vựng
• Biểu Diễn Automat Bằng Đồ Thị
• Automat Đoán Nhận R=(A  B) * Abb
• Vị Trí, Chức Năng, Nhiệm Vụ Của Giai Đoạn Phân Tích Cú Pháp

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

Bảng 2.5. Mô tả quá trình đoán nhận xâu

Ta có q = {2, 3}  F = {3} .

Vậy automat trên đoán nhận được từ w = aaabbbb.

2.4.3. Giải thuật sử dụng NFA

Input: NFAM và xâu vào w được kết thúc bởi $. Output: M có đoán nhận được w?

Process:

q:= ε-closure(q0); c:= get_char(); While c <> “$” do

Begin

q:= ε-closure((q,c));

c:= get_next_char();

End;

If q  F  then writeln (“nhan ra w”)

Else writeln („ không nhận ra w‟);

Ví dụ 2.19:

Cho Automat được biểu diễn bằng đồ thị như hình vẽ.

Sử dụng giải thuật trên để kiểm tra Automat đoán nhận từ w = aababb



2

a

3



Start

0



1





6



7

a

8

b

9

b

10

4

b



5



Hình 2.8. NFA với ε - dịch chuyển

Ta có thể trình bày giải thuật sử dụng automat trên đoán nhận w bằng bảng sau:

Bước

q = ε -closure((q,c))	c
khởi tạo	{0, 1, 2, 4, 6, 7}	a
1	{1, 2, 3, 4, 6, 7, 8}	a
2	{1, 2, 3, 4, 6, 7, 8}	b
3	{1, 2, 4, 5, 6, 7, 9}	a
4	{1, 2, 3, 4, 6, 7, 8}	b
5	{1, 2, 4, 5, 6, 7, 9}	b
6	{1, 2, 4, 5, 6, 7, 10}	$

Bảng 2.6. Mô tả quá trình đoán nhận xâu

Ta có q  F = {10} . Vậy automat trên đoán nhận được w = aababb.

NFA là trường hợp đặc biệt của NFA. Vì vậy ta vẫn có thể sử dụng giải thuật trên đối với NFA để nhận biết từ vị và trong trường hợp này ta luôn có ε-closure(T) = T với  T  Q.

2.5. Kỹ thuật biến đổi Automat

Automat hữu hạn đơn định và Automat hữu hạn không đơn định tương đương nhau về mặt ngôn ngữ, nghĩa là chúng cùng đoán nhận một tập chính quy. Tuy nhiên về phương diện cấu trúc và viết chương trình dịch thì Automat hữu hạn không đơn định phức tạp hơn nhiều so với Automat hữu hạn đơn định, vì vậy cần phải biến đổi Automat hữu hạn không đơn định về Automat hữu hạn đơn định.

Để biến đổi một Automat hữu hạn không đơn định thành một Automat đơn định tương đương với nó về mặt ngôn ngữ, trước hết cùng nhau nhắc lại một vài kiến thức sau:

Xét Automat hữu hạn M = < Q, , , q0, F > không đơn định

- Ta gọi tập ε-closure(q) là tập trạng thái mà M có thể đạt đến được từ trạng thái qQ khi Automat đọc vào từ rỗng .

ε-closure(q) = pQ *(q, ) = p

- Ta gọi tập ε-closure(T) là tập trạng thái mà M có thể đạt đến được từ một trạng thái bất kỳ qT với T  Q khi Automat đọc vào từ rỗng  là

ε-closure(T) = pQ *(q, ) = p; qT; TQ

= qT ε-CLOSURE(q) với T Q

- Ta gọi tập δ (T, a) là tập trạng thái mà M có thể đạt đến được từ một trạng thái bất kỳ qT với T  Q khi Automat đọc vào một ký hiệu vào a là

δ (T, a) = qT δ(q, a)

1) Ý tưởng của giải thuật

Giả sử có Automat hữu hạn không đơn định M = , , q0, F>. Ta cần phải xây dựng Automat hữu hạn đơn định là D = ‟, ‟, q‟0, F‟> tương đương đoán nhận cùng một ngôn ngữ. Khi đó mỗi trạng thái của Automat đơn định D sẽ ứng với một tập các trạng thái của Automat không đơn định M mà M có thể đạt đến được sau khi đã đọc một ký tự của từ vào. Thoạt đầu D có trạng thái bắt đầu là ε-closure(q0) và trạng thái kết thúc của D là trạng thái có chứa một trạng thái kết thúc của M. Quá trình tính ε-closure(T) là quá trình tìm các nút có thể đạt đến được trên đồ thị từ tập các nút xuất phát cho trước với các ký tự vào là các ký tự của bảng chữ cái vào .

2) Giải thuật biến đổi NFAvề DFA

Input: NFAM = , , q0, F>.

Output: DFA D = ‟, ‟, q‟0, F‟>; L(M) = L(D).

Process:

Bước 1: Xác định q‟0; ‟

- ‟ = ;

- Tính q‟0: A = ε-closure(q0);

- Đưa A vào tập trạng Q‟ và coi nó là trạng thái chưa đánh dấu T. Bước 2: Xác định Q‟ và ‟

Nếu trong Q‟ có trạng thái T chưa đánh dấu thì đánh dấu T

- Với mỗi a‟ thực hiện

+ Tính B = ε-closure((T,a));

+ Nếu B là trạng thái mới chưa có trong Q‟ thì đưa B vào Q‟;

+ Đưa vào bảng hàm chuyển ‟: ‟(T, a) = B.

Bước 3: Lặp lại bước 2 nếu Q‟còn trạng thái chưa đánh dấu. Bước 4: F‟ = {A Q‟ / A  F }

Bước 5: D = ‟, ‟, q‟0, F‟>

Begin

Q‟: = e_closure(q0);

‟:= 

Hình 2.9 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:= e-cloure((T, ai))

Q‟:= Q‟  {B};

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

i := i+1

Đánh dấu T

i := 1

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

Ví dụ 2.20:

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

Start

0



1

a

2

b

3

b

b



2.10. 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.10. 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*(b|)a+(b|)=b*a+(b| ) Áp dụng giải thuật, ta có:

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

- ‟ = {a, b};

- q‟0 = ε-closure(0) = {0, 1} = A; Q‟ = {A};

- Xét A:

+ ε-closure( (A, a)) = ε-closure(({0, 1}, a))

= ε-closure ((0, a)  (1, a)) = ε-closure({1, 2})

= ε-closure({1, 2}) = ε-closure(1)  ε-closure(2)

= {1} {2, 3} = {1, 2, 3} = B

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

+ ε-closure( (A, b)) = ε-closure(({0, 1}, b))

= ε-closure ( (0, b) (1, b)) = ε-closure({0,1} )

= ε-closure({0, 1}) = ε-closure(1)  ε-closure(1)

= {0,1} {1} = {0, 1} = A

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

- Xét B:

+ ε-closure( (B, a)) = ε-closure(({1, 2, 3}, a))

= ε-closure ( (1, a) (2, a) (3, a))

= ε-closure({1,2} )= ε-closure({1, 2})

= {1, 2, 3} = B

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

+ ε-closure( (B, b)) = ε-closure(({1, 2, 3}, b))

= ε-closure ( (1, b) (2, b) (3, b))

= ε-closure({3} ) = ε-closure({3})

= {3} = C

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

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

- Xét C:

+ ε-closure( (C, a)) = ε-closure((3, a)) = 

+ ε-closure( (C, b)) = ε-closure((3, b)) = 

- F‟ = {B, C}

Vậy D = < Q‟, ‟, ‟, q‟0, F‟ >. Trong đó: Q‟ = {A, B, C} ;

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

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

F‟ = {B, C}.

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

Start

A

a

B

b

C

b a

Hình 2.11. 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 = ε-closure(q0) = ε-closure(0) = {0, 1} = A;

- ‟ = {a, b};

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

Bước

Đánh dấu T	ai	B = ε-closure((T, ai))	Bsung vào Q‟	Bsung vào ‟
Kt			{0, 1}	A
1	A	a	{1, 2, 3}	B	‟(A, a) = B
		b	{0, 1}		‟(A, b) = A
2	B	a	{1, 2, 3}		‟(B, a) = B
		b	{3}	C	‟(B, b) = C
3	C	a	
		b	

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

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

b) Xét Automat hữu hạn M = < Q, , , q0, F > không đơn định có  dịch chuyển.

Với Q =0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; q0 =0; F = 10;  = a,b; hàm 

cho trong hình 2.15.

Có thể kiểm tra lại rằng tập ngôn ngữ đoán nhận bởi Automat hữu hạn M là tập N(M) = (a b)*abb.



2

a

3



Start

0



1



6



7

a

8

b

9

b

4

b



5



10



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

Để xây dựng automat hữu hạn đơn định D đoán nhận cùng ngôn ngữ với Automat M, ta sử dụng giải thuật trên.

- Tính q‟0 = ε-closure(q0) = ε-closure(0) = 0, 1, 2, 4, 7 = A;

- ‟ = {a, b};

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

Bước

Đánh dấu T	ai	B = ε-closure((T, ai))	Bổ sung vào Q‟	Bổ sung vào ‟
Kt			{0, 1, 2, 4, 7} = A	A
1	A	a	{1, 2, 3, 4, 6, 7, 8} = B	B	‟(A, a) = B
		b	{1, 2, 4, 5, 6, 7} = C	C	‟(A, b) = C
2	B	a	{1, 2, 3, 4, 6, 7, 8} = B		‟(B, a) = B
		b	{1, 2, 4, 5, 6, 7, 9} = D	D	‟(B, b) = D
3	C	a	{1, 2, 3, 4, 6, 7, 8} = B		‟(C, a) = B
		b	{1, 2, 4, 5, 6, 7} = C		‟(C, b) = C
4	D	a	{1, 2, 3, 4, 6, 7, 8}= B		‟(D, a) = B
		b	{1, 2, 4, 5, 6, 7, 10} = E	E	‟(D, b) = E
5	E	a	{1, 2, 3, 4, 6, 7, 8}= B		‟(E, a) = B
		b	{1, 2, 4, 5, 6, 7} = C		‟(E, b) = C

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

- Xác định F‟ = {E}

b

C

b

a

a

b

Start

A

a

B b

D

b

E

a a

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

Chú ý:

NFA là trường hợp đặc biệt của NFA. Vì vậy ta vẫn có thể sử dụng giải thuật trên để biến đổi NFA về DFA. Tuy nhiên, trong trường hợp này luôn luôn có ε-closure(T) = T với  T  Q. Vì vậy, có thể đưa ra giải thuật cụ thể trong trường hợp này như sau.

3) Giải thuật biến đổi NFA về DFA

Input: NFA M = < Q, , , q0, F >.

Output: DFA D = < Q‟, ‟, ‟, q‟0, F‟ >; L(M) = L(D).

Process:

Bước 1: Xác định q‟0; ‟

- ‟ = ;

- Tính q‟0: A = q0;

- Đưa A vào tập trạng Q‟ và coi nó là trạng thái chưa đánh dấu T. Bước 2: Xác định Q‟ và ‟

Nếu trong Q‟ có trạng thái T chưa đánh dấu thì đánh dấu T

- Với mỗi a‟ thực hiện

+ Tính B = (T,a);

+ Nếu B là trạng thái mới chưa có trong Q‟ thì đưa B vào Q‟;

+ Đưa vào bảng hàm chuyển ‟: ‟(T, a) = B.

Bước 3: Lặp lại bước 2 nếu Q‟còn trạng thái chưa đánh dấu. Bước 4: F‟ = {A Q‟ / A  F }

Bước 5: D = < Q‟, ‟, ‟, q‟0, F‟>