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

NFA M ({q0, q1, q2, q3, q4}, {0, 1}, d, q0, {q2, q4}) với hàm chuyển d như sau :

Xét chuỗi nhập w = 01001

Ta có :d (q0, 0) = {q0, q­3}

d (q0, 01) = d(d(q0, 0),1) = d({q0, q­3},1) = d (q0, 1) È d (q3, 1) = {q0, q­1}

Tương tự , ta có thể tính :

d (q0, 010) = {q0, q­3}

d (q0, 0100) = {q0, q­3, q­4}

và d (q0, 01001) = {q0, q­1, q­4}

Do q4  F nên w  L (M).

Câu hỏi :

?

1. Hãy cho nhận xét về điểm khác biệt quan trọng giữa DFA và NFA ?
2. Theo bạn, dạng đơn định hay không đơn định sẽ dùng nhận dạng một chuỗi

dễ dàng hơn ?

Sự tương đương giữa dfa và nfa

Vì mỗi DFA là một NFA, nên rõ ràng lớp ngôn ngữ được chấp nhận bởi NFA cũng bao gồm các tập chính quy (đây chính là ngôn ngữ được chấp nhận bởi DFA ). Tuy nhiên, không có cơ sở để nói rằng NFA chỉ chấp nhận duy nhất các tập hợp này. Điều đó cho thấy DFA có thể mô phỏng được hoạt động của NFA, nghĩa là với mỗi NFA, ta có thể xây dựng một DFA tương đương (chấp nhận cùng một ngôn ngữ với nó). Đặt một DFA mô phỏng hoạt động của NFA là cho phép các trạng thái của DFA tương ứng với tập các trạng thái của NFA. Tại mỗi thời điểm, DFA lưu giữ trong bộ điều khiển tất cả các trạng thái mà NFA có thể chuyển đến khi đọc cùng một input như DFA.

ĐỊNH LÝ 3.1 : Nếu L là tập được chấp nhận bởi một NFA thì tồn tại một DFA chấp nhận L.

Chứng minh

Đặt M (Q, , , q0, F) là NFA chấp nhận L.

Ta xây dựng DFA M' (Q’, , ’, q0’, F’) tương đương như sau:

- Các trạng thái của M’ là tất cả các tập hợp con của tập trạng thái của M, hay Q’= 2Q. Tại mỗi thời điểm, M’ sẽ lưu giữ trong trạng thái của nó tất cả các trạng thái có thể của M. Một phần tử trong Q’ được ký hiệu là [q1, q2,..., qi], trong đó các trạng thái q1, q2,..., qi  Q. Ta xem [q1, q2,..., qi]là một trạng thái đơn của DFA tương ứng với một tập trạng thái của NFA.

- q0’ = [q0].

- F' là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết thúc trong tập F của M.

- Ta định nghĩa hàm chuyển ’ như sau :

d’ ([q1, q2,..., qi], a) = [p1, p2,..., pj]nếu và chỉ nếu  ({q1, q2,..., qi }, a) = {p1, p2,..., pj}

Bây giờ ta chứng minh quy nạp theo độ dài của chuỗi nhập x rằng:

d’(q0’, x) = [q1, q2,..., qi] Û d(q0, x) = {q1, q2,..., qi} (1)

Với x= 0 , ta có x =  và q0’ = [q0] nên (1) hiển nhiên đúng

Giả sử (1) đúng với các chuỗi nhập có độ dài tới m.

Xét chuỗi nhập có độ dài m + 1, đặt chuỗi này là xa với a  , ta có :

d’(q0’, xa) = d’(d’(q0’, x), a)

Theo định nghĩa :

d’([p1, p2,..., pi], a) = [r1, r2,..., rk]Û d({p1, p2,..., pj}, a) = {r1, r2,..., rk}.

Mặt khác theo giả thiết quy nạp d’(q0’, x) = [p1, p2,..., pj] Û d(q0, x) = {p1, p2,..., pj}, nên thay vào ta có : d’(q0’, xa) = [r1, r2,..., rk]Û d(q0, xa) = {r1, r2,..., rk}.

Dễ thấy rằng d’(q0’, x)  F' khi và chỉ khi d(q0, x) có chứa ít nhất một trạng thái  F.

Vậy L(M) = L(M’)

Vì NFA và DFA chấp nhận cùng các tập hợp, nên ta sẽ không phân biệt chúng trừ khi điều đó thật sự cần thiết, sẽ đơn giản hơn để hiểu cả hai cùng là ôtômát đơn định.

Thí dụ 3.5 : Cho NFA M ({q0, q1}, {0, 1}, d, q0, {q1}) với hàm chuyển d như sau :