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

Automat Hữu Hạn Không Đơn Định-Nfa (Nondeterministic Finite Automata)


Bước

q

c

khởi tạo

0

b

1

0

b

2

0

a

3

1

a

4

1

a

5

1

b

6

2

b

7

3

$

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

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

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


Bảng 2.4. Quá trình Automat đoán nhận xâu

Ta có q = 3 F. Vậy automat trên đoán nhận được từ w = bbaaabb.

- w = bbaaaaab$


Ta trình bày giải thuật sử dụng automat đơn định đoán nhận w bằng bảng sau:


Bước

q

c

khởi tạo

0

b

1

0

b

2

0

a

3

1

a

4

1

a

5

1

a

6

1

a

7

1

b

8

2

$

Bảng 2.5. Quá trình Automat đoán nhận xâu

Ta có q = 2 F. Vậy automat trên không đoán nhận được từ w = bbaaaaab.


2.1.3. Automat hữu hạn không đơn định-NFA (Nondeterministic Finite Automata)

Xét một dạng sửa đổi mô hình DFA có thể lựa chọn một trong nhiều hơn một phép chuyển từ một trạng thái trên cùng một ký hiệu vào để di chuyển đến đến trạng thái tiếp theo. Mô hình mới này gọi là automat hữu hạn không đơn định (NFA).

1) Định nghĩa

Cho Automat hữu hạn M = <Q, , , q0, F >, ta gọi M là Automat hữu hạn không đơn định nếu: a và q Q sao cho (q, a) >1 và hàm chuyển có dạng 2. Cụ thể:

Automat hữu hạn không đơn định 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 qQ, a và p 2Q (p Q). Như vậy, δ(q, a) là tập hợp p tất cả các trạng thái piQ sao cho có phép chuyển trên nhãn a từ trạng thái q tới pi .

Ví dụ:

Cho automat hữu hạn không đơn định (NFA) M = <Q, , , q0, F> trong đó:

- Q = {q , q , q , q , q };

0 1 2 3 4

- {0, 1};

- 

(q0, 0) = {q0, q3};

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


(q1, 1) = {q };

2

(q2, 0) = {q };

2

(q2, 1) = {q };

2

(q3, 0) = {q };

4

(q4, 0) = {q };

4

(q4, 1) = {q };

4

- q0 = q0;

- F = {q , q }.

2 4

- Biểu diễn NFA trên bằng bảng, ta có


Q

0

1

q0

{q ,q }

0 3

{q ,q }

0 1

q1


{q }

2

q2

{q }

2

{q }

2

q3

{q }

4


q4

{q }

4

{q }

4


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

- Biểu diễn NFA trên bằng đồ thị, ta có

1

1

1

q1

1

q2

Start

1

q

0

0

q3

0

0

q4

0

0

Hình 2.6. Đồ thị của NFA


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

Để có thể mô tả cách hình thức hoạt động của NFA trên một xâu vào, ta mở rộng hàm chuyển δ để áp dụng đối với một trạng thái trên một xâu. Ta định nghĩa hàm chuyển mở rộng δ* là một ánh xạ từ Q × Σ* → Q với ý nghĩa δ*(q, w) là tập trạng thái mà NFA có thể chuyển đến từ trạng thái q trên xâu vào w:

1. δ*(q, ε) = {q} ;

2. δ*(q, wa) = δ(δ*(q, w), a) với q Q; w Σ* và a Σ 3. δ*(P, a) = δ*(q, a) với P Q.

q P


Suy ra:


δ*(P, a) = q P δ(δ* (q, ), a) = q P δ(q, a) Hay δ*(P, a) = q P δ(q, a) với P Q.

Ví dụ:


Cho automat trong ví dụ trên biểu diễn bằng đồ thị ở hình 2.6. Hãy tính *(q0, 01001).

Áp dụng công thức 2 ở trên, ta có:

*(q0, 01001) =  q0, 01001

=  q0, 010), 01

=  q0, 01), 0), 01

=  q0, 0), 1), 0), 01

=  q0, ), 0), 1), 0), 01

= q0, 0), 1), 0), 01

(q0, 0) = {q0, q3};

q0, 0), 1) = {q0, q3}, 1) = q0, 1) q3, 1) = {q0, q1}∅

= {q0, q1};


∅

q0, 0), 1), 0) = {q , q }, 0) = q , 0) q , 0) = {q , q }

0 1 0 1 0 3


= {q , q };

0 3


q0, 0), 1), 0), 0{q , q }, 0

0 3


= δ (q , 0) δ (q , 0) = {q , q } {q } ={q , q , q };

0 3 0 3 4 0 3 4


q0, 0), 1), 0), 01 δ({q , q , q }, 1) = δ (q , 1) δ (q , 1)δ (q , 1)

0 3 4 0 3 4


∅

= {q , q } {q } ={q , q , q };

0 1 4 0 1 4


δ*(q , 01001) = {q , q , q };

0 0 1 4


Tương tự như DFA, NFA cũng hoạt động với một bộ điều khiển gồm hữu hạn trạng thái và một đầu đọc đọc các ký hiệu trên xâu vào. Tuy nhiên, tại mỗi thời điểm, bộ điều khiển có thể chứa một tập các trạng thái. Khi đó, để có sự lựa chọn

trạng thái tiếp theo, chẳng hạn như từ trạng thái q trên ký hiệu vào 0 ở ví dụ trên, ta

0

phải tưởng tượng như có các bản sao của automat đang thực hiện đồng thời. Mỗi trạng thái tiếp theo mà automat có thể chuyển đến sẽ tương ứng với một bản sao của automat mà tại đó bộ điều khiển đang chứa trạng thái đó.

Chẳng hạn, với xâu 01001, ta có:

q0 0 q01

q00

q00

q0 1 q0


0

1

0

0

1

q3 q1 q3 q3 q1


0

q4

1

q4

Hình 2.7. Quá trình suy diễn để đoán nhận xâu trong NFA


3) Ngôn ngữ đoán nhận bởi automat không đơn định


Cho Automat hữu hạn không đơn định M = <Q, , , q0, F>, ta gọi ngôn ngữ đoán nhận bởi Automat hữu hạn không đơn định M là tập:


L(M) = w Σ* *(q0,w) = q F và w*

Hay L(M) = {w * | δ*(q0, w) có chứa một trạng thái trong F }

Như vậy, ngôn ngữ đoán nhận bởi Automat hữu hạn không đơn định M là tập tất cả các xâu vào w* nếu tồn tại một dãy các phép chuyển (đường đi) sao cho khi Automat ở trạng thái ban đầu q0, nhận từ vào w thì nó có thể chuyển dịch về một trong các trạng thái kết thúc thuộc tập F.

Chú ý rằng có thể xem automat hữu hạn đơn định - DFA là một trường hợp đặc biệt của NFA, trong đó với mỗi trạng thái và mỗi ký hiệu vào chỉ có duy nhất một lựa chọn phép chuyển sang trạng thái tiếp theo. Vì thế trong DFA, với một xâu vào w và một trạng thái bắt đầu q0, chỉ có đúng một đường đi nhãn w bắt đầu từ q0. Để xác định xâu w có được đoán nhận bởi DFA hay không chỉ cần kiểm tra đường đi này. Nhưng đối với NFA, có thể có nhiều đường đi có nhãn là w bắt đầu từ q0 và do đó tất cả phải được kiểm tra để thấy có hay không có đường đi tới trạng thái kết thúc. Do đó, một xâu vào w = a1 a2 ... an được đoán nhận bởi một NFA nếu có tồn tại một dãy các phép chuyển, tương ứng với xâu vào, từ trạng thái bắt đầu đến trạng thái kết thúc. Như vậy, để kiểm tra một xâu vào w = a1 a2 ... an được đoán nhận bởi một NFA hay không ?. Ta phải tính *(q0,w).

*(q0,w) = *(q0, a1a2 ... an) =  q0, a1 an-1an

=  q0, a1 an-1an

=  q1, a2 an-1an

= …


= q n-2, an-1an

= qn-1, an

= qn.

Nếu qn F ≠ thì w N(M); ngược lại qn F thì w N(M). Ở đây q1 q2 qn Q.


Ví dụ: Cho automat hữu hạn không đơn định (NFA): M = <Q, , , q0, F> trong ví dụ trên. Hãy kiểm tra xem xâu w = 01001 có thuộc ngôn ngữ L(M) hay không ?.

Ta có: δ (q , 0) = {q , q };

0 0 3


∅

δ({q , q },1) = δ (q , 1) δ (q , 1) = {q , q } = {q , q };

0 3 0 3 0 1 0 1


∅=

δ({q , q }, 0) = δ (q , 0) δ (q , 0) = {q , q } {q , q };

0 1 0 1 0 3 0 3


δ({q , q }, 0) = δ (q , 0) δ (q , 0) = {q , q } {q } ={q , q , q };

0 3 0 3 0 3 4 0 3 4


∅

δ({q , q , q }, 1) = δ (q , 1) δ (q , 1)δ (q , 1) = {q , q } {q }

0 3 4 0 3 4 0 1 4


={q , q , q };

0 1 4


δ*(q , 01001) = {q , q , q };

0 0 1 4


Do {q , q , q } {q } = {q } ≠ nên w N(M).

0 1 4 4 4


Automat này đoán nhận được tất cả các xâu có hai số 0 liên tiếp hoặc hai số 1 liên tiếp.

Từ các kết quả trên, ta có giải thuật sử dụng DFA để đoán nhận xâu của ngôn ngữ.


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

Input : xâu vào w kết thúc bởi $

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

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

Process

q := q0 ;

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

While c < > $ do begin

q := δ(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" )

Sử dụng giải thuật trên với automat hữu hạn được cho bằng đồ thị sau để đoán nhận các xâu: w = aaabbbb$


a b

Start

0

a

1

b

2

b

3

a

Hình 2.8. Đồ thị biểu diễn Automat

Ta trình bày giải thuật sử dụng automat hữu hạn không đơn định đoán nhận w bằng bảng sau:


Bước

q

c

khởi tạo

0

a

1

{0, 1}

a

2

{0, 1}

a

3

{0, 1}

b

4

{2}

b

5

{2, 3}

b

6

{2, 3}

b

7

{2, 3}

$


Bảng 2.7. 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.

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

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