Sự Tương Đương Giữa Nfa Có Và Không Có Ε-Dịch Chuyển

chuyển dịch (đường đi) từ trạng thái bắt đầu đến một trạng thái kết thúc khi nhận

được xâu vào là w. Chẳng hạn, xâu 002 được đoán nhận bởi NFA trên bởi vì có đường đi q , q , q , q , q với các cung có nhãn tương ứng 0, 0, ε, 2.

0 0 1 2 2

Ví dụ: Đồ thị của một NFA với ε-dịch chuyển:

Start

q0

0

q1



q2

0 1 2

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

1) Định nghĩa

Automat hữu hạn không đơn định với ε-dịch chuyển (NFA với ε-dịch chuyển) là một hệ thống gồm 5 thành phần; ký hiệu là M = <Q, , , q0, F> trong đó:

Q - Tập hữu hạn khác rỗng các trạng thái.

 - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).

 - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng:

: Q  ( {})  2Q

(q, a) p q0 - Là trạng thái bắt đầu; q0 Q.

F - Tập con của Q là tập các trạng thái kết thúc.

Nếu p là ảnh của (q, a) qua ánh xạ  thì ký hiệu là (q,a) = p; với qQ; a{} và p 2Q (p  Q).

Như vậy, NFA với ε-dịch chuyển là một NFA được bổ sung thêm phép chuyển trạng thái trên nhãn rỗng và ký hiệu δ(q, a) gồm tất cả các trạng thái p sao cho có phép chuyển trên nhãn a từ q tới p, trong đó a là một ký hiệu thuộc Σ hoặc là ε.

Ví dụ 1:

Cho NFA M = <Q, , , q0, F> với Q = {q0, q1, q2};



q0 = q0;

F = { q2};



q0 q0

q0 q1

q11 q1

q1 q2

q22 q2

- Biểu diễn NFA trên dưới dạng đồ thị:

Start

q0



q1



q2

0 1 2

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

- Biểu diễn NFA trên dưới dạng bảng:

 {}

Q

0	1	2	
q 0	{q } 0			{q } 1
q 1		{q } 1		{q } 2
q 2			{q } 2

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

• Biểu Diễn Automat Bằng Đồ Thị
• Automat Hữu Hạn Không Đơn Định-Nfa (Nondeterministic Finite Automata)
• Automat Hữn Hạn Đơn Định Đoán Nhận Ngôn Ngữ L
• Một Số Tính Chất Đại Số Của Biểu Thức Chính Quy
• Sự Tương Đương Giữa 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.

Bảng 2.11. Bảng chuyển trạng thái

2) Hàm chuyển trạng thái mở rộng

Ta mở rộng hàm chuyển δ thành hàm chuyển δ* ánh xạ từ Q × Σ* → 2Q. δ*(q, w) chứa tất cả các trạng thái p sao cho có thể đi từ q tới p theo đường đi khi nhận vào xâu w (có thể chứa cạnh nhãn ε).

Ta sử dụng hàm

-CLOSURE(q) là tập hợp các trạng thái p sao cho có đường đi từ một trạng thái q tới p khi M nhận vào từ rỗng .

Ví dụ 2:

Trong hình trên, ε-CLOSURE(q0) = {q0, q1, q2}.

Vì đường đi chỉ có một đỉnh q (không có cung trên đường đi) là đường đi từ

0

q tới q có tất cả các cạnh nhãn là ε. Đường đi q , q chỉ ra rằng q thuộc ε-

0 0 0 1 1

CLOSURE(q ) và đường đi q , q , q chỉ ra rằng q thuộc ε-CLOSURE(q ).

0 0 1 2 2 0

-CLOSURE(T) là tập hợp các trạng thái p sao cho có thể đi từ mỗi trạng thái q T tới trạng thái p khi M nhận vào từ rỗng  với T  Q.

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

qT

* * Q

Ta định nghĩa hàm δ mở rộng là một ánh xạ δ : Q × Σ → 2

1. δ*(q, ε) = ε-CLOSURE(q)

*

thoả mãn điều kiện:

*

2. δ (q, wa) = ε-CLOSURE(P), trong đó tập P = {p | có r trong δ (q, w) sao

*

cho p δ(r, a)}, w  Σ và a  Σ.

Hay δ*(q, wa) = ε-CLOSURE(δ(δ*(q, w), a))

 δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a)) với mọi q Q và a 

= ε-CLOSURE(δ(ε- closure(q), a)) Ta mở rộng δ và δ* trên tập hợp các trạng thái T với T  Q như sau:

3. δ* (T, a) = qT δ*(q, a)

Ví dụ 3: Cho NFAε trong ví dụ 1. Tính δ*(q0, 012) . Ta có:

δ*(q0, ε) = ε-CLOSURE(q0) = {q0, q1, q2}

Vậy δ*(q0, 0) = ε-CLOSURE(δ(δ*(q0, ε), 0)

= ε-CLOSURE(δ({q0, q1, q2}, 0))

= ε-CLOSURE(δ(q0, 0)  δ(q1, 0)  δ(q2, 0))

= ε-CLOSURE({q0} ∅ ∅ )

= ε-CLOSURE({q0}) = {q0, q1, q2}

và δ*(q0, 01) = ε-CLOSURE(δ(δ*(q0, 0), 1))

= ε-CLOSURE(δ({q0, q1, q2}, 1))

= ε-CLOSURE(δ(q0, 1)  δ(q1, 1)  δ(q2, 1))

1

= ε-CLOSURE(∅  {q } ∅ )

= ε-CLOSURE({q }) = {q , q }

1 1 2

 δ*(q , 012) = ε-CLOSURE(δ( δ*(q , 01), 2))

0 0

= ε-CLOSURE(δ({q , q }, 2))

1 2

= ε-CLOSURE(δ(q , 2)  δ(q , 2))

1 2

∅

= ε-CLOSURE(  {q })

2

= ε-CLOSURE({q }) = {q }

2 2

Nhận xét:

δ*(q, a) và δ(q, a) không bằng nhau vì δ*(q, a) gồm tất cả các trạng thái có thể chuyển đến được từ q trên nhãn a gồm cả đường đi nhãn ε (a*), trong khi đó δ(q, a) chỉ gồm các trạng thái có thể đến được từ q chỉ bằng các cung nhãn a (a). Tương tự δ*(q, ε) có thể cũng không bằng δ(q, ε). Vì vậy ta phải phân biệt ký hiệu δ và δ* đối với NFA với ε-dịch chuyển.

3) Ngôn ngữ được đoán nhận bởi NFAε

Cho NFAε M = <Q, Σ, δ, q , F>, ngôn ngữ được đoán nhận bởi NFAε M là tập hợp

0

các xâu L(M) được xác định như sau:

L(M) = {w  Σ* | δ*(q , w) F  }

0

4) Giải thuật mô phỏng hoạt động của một NFAε

Input: Xâu vào w được kết thúc bởi $.

Output: Câu trả lời "YES" nếu NFAε đoán nhận xâu w

và "NO" nếu ngược lại.

phương pháp

q:= ε-CLOSURE(q0);

c:= getchar() ; {c là ký hiệu vào đầu tiên}

While c <> $ do begin

q:= ε-CLOSURE(δ(q, c));

c:= nextchar() ; {c là ký hiệu vào được đọc tiếp theo}

end

Ví dụ:

If q  F  then write ("YES")

else write ("NO");

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

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.15. 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.12. Mô tả quá trình đoán nhận xâu

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

2.1.6. Sự tương đương giữa NFA có và không có ε-dịch chuyển

1) Định lý

Nếu L được đoán nhận bởi một NFA có ε-dịch chuyển thì L cũng được đoán nhận bởi một NFA không có ε-dịch chuyển.

Chứng minh:

Đặt M = <Q, Σ, δ, q , F> là NFA với ε-dịch chuyển.

0

Ta xây dựng NFA M‟= <Q, Σ, δ‟, q , F‟> tương đương không có ε-dịch

0

chuyển, trong đó:

- F‟ =

F  {q } nếu ε-CLOSURE(q )  F 

0 0

F trong các trường hợp còn lại

- δ‟(q, a) = δ*(q, a) với q  Q và a  Σ. Chú ý rằng M‟ không có ε-dịch chuyển .

Ta chứng minh bằng quy nạp trên | w | rằng δ‟(q , w) = δ*(q , w).

0 0

Tuy nhiên, điều đó có thể không đúng với w = ε vì δ‟(q , ε) = {q } trong khi đó

0 0

δ*(q , ε) = ε-CLOSURE(q ). Do đó, cơ sở quy nạp bắt đầu với độ dài xâu là 1.

0 0

Với | w | = 1 thì w là một ký tự a và δ‟(q, a) = δ(q, a) theo định nghĩa δ‟.

Giả sử với | w | = n (n >1) ta đã có δ‟(q0, w) = δ*(q0, w). Ta phải chứng minh δ‟(q0, w) = δ*(q0, w) với | w | = n + 1 . Tức là δ‟(q0, wa) = δ*(q0, wa) với a là một ký tự trong Σ.

Ta có δ‟(q, wa) = δ‟(δ‟(q0, w), a)

Theo giả thiết quy nạp thì δ‟(q0, w) = δ*(q0, w). Đặt δ*(q0, w) = T, ta cần chỉ ra rằng δ*(T, a) = δ*(q0, wa).

Ta có δ‟(T, a) = qT δ‟(q, a) = qT δ*(q, a).

Hơn nữa vì T = δ*(q0, w) nên qT δ*(q, a) = δ*(q0, wa) ( theo quy tắc 2 trong định nghĩa δ mở rộng).

Vậy δ‟(q0, wa) = δ*(q0, wa)

Để chứng minh đầy đủ, ta còn phải chỉ ra rằng δ‟(q0, w) F‟  nếu và chỉ nếu δ*(q0, w) F  .

Nếu w = ε thì điều đó hiển nhiên đúng (theo định nghĩa của F‟)

Nếu w ≠ ε thì ta đặt w = wa với a  Σ. Nếu δ*(q , w) F  F thì chắc chắn

0

δ‟(q , w) F‟  chứa cùng trạng thái trong F‟. Ngược lại, nếu δ‟(q , w) chứa một

0 0

trạng thái trong F‟ khác hơn q thì δ*(q , w) phải chứa một trạng thái trong F (vì tập

0 0

F và F‟ chỉ chênh lệch nhau trạng thái q ). Nếu δ‟(q , w) có chứa trạng thái q và q

0 0 0 0

cũng là một trạng thái thuộc tập trạng thái kết thúc F thì vì δ*(q , w) =

0

ε-CLOSURE(δ(δ (q , w),a)), nên trạng thái chung trong ε-CLOSURE(q ) và trong F

0 0

phải ở trong δ*(q , w).

0

Từ định lý, ta có giải thuật chuyển NFA có  - dịch chuyển về NFA không có

 - dịch chuyển.

2) Giải thuật chuyển NFA về DFA

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

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

Process:

- Q‟ = Q;

- Σ‟ = Σ;

- q’0 = q

0

F  {q } nếu ε-CLOSURE(q )  F 

- F‟ = 0 0

F nếu ε-CLOSURE(q )  F = 

0

Ví dụ:

- Hàm chuyển δ‟:

Với mỗi q  Q‟ thực hiện Với mỗi a ‟ tính

δ‟(q, a) = δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a))

= ε-CLOSURE(δ(e- closure(q), a)) = p

0

1

2

Start

q0



q1



q2

Chuyển NFA với ε-dịch chuyển ở hình sau sang dạng NFA không có chứa

ε-dịch chuyển.

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

Ta xây dựng NFA tương đương M‟= <Q, Σ, δ‟, q , F‟> đoán nhận L(M) với:

0

- Q = {q , q , q };

0 1 2

- Σ = {0, 1, 2};

- Trạng thái bắt đầu: q

0

- F‟ = {q , q } do ε-CLOSURE(q ) = {q , q , q }  F = {q }

0 2 0 0 1 2 2

- Hàm chuyển δ‟ của M‟ được xác định theo công thức:

δ‟(q, a) = δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a)) với mọi q Q và a 

= ε-CLOSURE(δ(ε- closure(q), a)) Kết quả bảng chuyển trạng thái được chỉ ra trong bảng sau:



Q

0	1	2
q 0	{q , q , q } 0 1 2	{q , q } 1 2	{q } 2
q 1		{q , q } 1 2	{q } 2
q 2			{q } 2

Bảng 2.13. Bảng chuyển trạng thái

Biểu diễn NFA trên bằng đồ thị

Start

q0 0, 1

q1

1, 2

q2

0, 1, 2

0 1 2

Hình 2.17. NFA tương đương với NFA

2.2. Biểu thức chính quy (RE: Regular Expressions)

Lớp ngôn ngữ được đoán nhận bởi một automat hữu hạn cũng có thể được mô tả thông qua một dạng biểu thức ngắn gọn và súc tích gọi là biểu thức chính quy. Trong phần này, chúng ta sẽ giới thiệu sự kết hợp của các phép toán hợp, nhân ghép và lấy bao đóng Kleene trên các tập hợp xâu để định nghĩa biểu thức chính quy và chứng tỏ rằng lớp ngôn ngữ được đoán nhận bởi một automat hữu hạn thì thực sự là lớp ngôn ngữ được mô tả bởi biểu thức chính quy.