0.2 Ôtômat hữu hạn và biểu thức chính quy  (Page 7/16)

?

Hãy so sánh sự khác biệt giữa hàm chuyển  và * ?

Nhận xét : *(q, a) và (q, a) không nhất thiết 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 e, trong khi đó d(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. Tương tự *(q, e) có thể cũng không bằng (q, e). Vì vậy ta phải phân biệt ký hiệu  và * đối với NFA với e-dịch chuyển.

Ngôn ngữ được chấp nhận bởi NFA:

Ta định nghĩa L(M), ngôn ngữ được chấp nhận bởi NFA M = (Q, , , q0, F) là tập hợp các chuỗi :

L(M) = {w  *(q0, w) có chứa ít nhất một trạng thái trong F}

Thí dụ 3.8 : Xét sơ đồ chuyển của hình 3.4.

Theo khái niệm hình thức, ta có NFA M ({q0, q1, q2}, {0, 1, 2}, , q0, {q2}) với hàm chuyển  như sau :

Xét chuỗi nhập w = 012.

Ta cần tính *(q0, 012)

Ta có : *(q0, e) = e-CLOSURE(q0) = {q0, q1, q2}

vậy *(q0, 0) = e-CLOSURE((*(q0, e), 0)

= e-CLOSURE(d({q0, q1, q2}, 0))

= e-CLOSURE(d(q0, 0) È d(q1, 0) È d(q2, 0))

= e-CLOSURE({q0} È Æ È Æ )

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

và *(q0, 01) = e-CLOSURE((*(q0, 0), 1))

= e-CLOSURE(d({q0, q1, q2}, 1))

= e-CLOSURE(d(q0, 1) È d(q1, 1) È d(q2, 1))

= e-CLOSURE(Æ È {q1} ÈÆ )

= e-CLOSURE({q1}) = {q1, q2}

 *(q0, 012) = e-CLOSURE(d( *(q0, 01), 2))

= e-CLOSURE(d({q1, q2}, 2))

= e-CLOSURE(d(q1, 2) È d(q2, 2))

= e-CLOSURE(Æ È {q2})

= e-CLOSURE({q2}) = {q2}

Do *(q0, 012) có chứa trạng thái q2  F nên chuỗi w  L(M).

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

. Input : Chuỗi nhập x được kết thúc bởi $.

. Output : Câu trả lời "YES" nếu NFA chấp nhận chuỗi x và "NO" nếu

ngược lại.

. Giải thuật :

q := e-CLOSURE(q0);

c := nextchar ; { c là ký hiệu nhập được đọc tiếp theo }

While c<>$ do

begin

q := e-CLOSURE(d(q, c));

c := nextchar ;

end

If q in F then write ("YES") else write ("NO");

Sự tương đương giữa nfa có và không có e-dịch chuyển

Tương tự như NFA, khả năng có thể thực hiện phép chuyển trên nhãn e của NFAe cũng không làm cho NFAe chấp nhận được các tập hợp không chính quy. Ta có thể dẫn chứng điều này bằng cách mô phỏng hoạt động của một NFAe bởi một NFA không có e-dịch chuyển.

ĐỊNH LÝ 3.2 : Nếu L được chấp nhận bởi một NFA có e-dịch chuyển thì L cũng được chấp nhận bởi một NFA không có e-dịch chuyển.

Chứng minh

Đặt M (Q, , , q0, F) là NFA với e-dịch chuyển.

Ta xây dựng NFA M’(Q, , ’, q0, F’) tương đương không có e-dịch chuyển, trong đó:

F  {q0} nếu e-CLOSURE(q0) chứa một trạng thái thuộc F

. F’ =

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

. ’(q, a) là *(q, a) với q  Q và a  . Chú ý rằng M’ không có e-dịch chuyển nên ta có thể dùng ’ thay cho *’, nhưng phải phân biệt  và *.

Ta chứng minh bằng quy nạp trên  x  rằng ’(q0, x) =  *(q0, x). Tuy nhiên, điều đó có thể không đúng với x = e vì ’(q0, e) = {q0} trong khi  *(q0, e) = e-CLOSURE(q0). Do đó, cơ sở quy nạp bắt đầu với độ dài chuỗi là 1.

Với | x | = 1 thì x là một ký hiệu a và ’(q, a) =  *(q, a) theo định nghĩa ’.

Xét | x |>1: đặt x = wa với a là một ký hiệu trong .

Ta có ’(q, wa) = ’(’(q0, w), a)