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

d(q0, 0) = {q0, q1},d(q0,1) = {q1},d(q1, 0) = , d(q1, 1) = {q0, q1}

Ta xây dựng DFA tương đương M’ (Q’, {0, 1}, d’, [q0], F’) chấp nhận L(M) như sau :

. Q’ : chứa tất cả các tập con của {q0, q1}, vậy Q’ = {[q0], [q1], [q0, q1], }

. Hàm chuyển d’ :

Vì d(q0, 0) = {q0, q­1} nên d’([q0], 0) = [q0, q­1]

Tương tự : d’([q0], 1) = [q­1]

d’([q­1], 0) = 

d’([q­1], 1) = [q­0, q­1]

Mặt khác : d’(, 0) = d’(, 1) = 

Cuối cùng : d’([q0, q1],0) = [q0, q­1]

( vì d({q0, q1},0) = d(q0, 0)  d(q1, 0) = {q0, q­1}   = {q0, q­1})

d’([q0, q1], 1) = [q0, q­1]

( vì d({q0, q1},1) = d(q0, 1)  d(q1, 1) = {q­1}  {q0, q­1} = {q0, q­1})

. Tập trạng thái kết thúc F' = {[q­1], [q0, q­1]}

Thực tế, có rất nhiều trạng thái của NFA không có hàm chuyển đến từ trạng thái bắt đầu [q0]. Do đó, thông thường, cách tốt nhất là ta nên xây dựng DFA tương đương bắt đầu từ trạng thái [q0]và thêm vào các trạng thái mới cho DFA chỉ khi có các hàm chuyển từ một trạng thái đã được thêm vào trước đó.

Câu hỏi :

?

Bạn có nhận xét gì về kích thước giữa một DFA và một NFA tương đương với nó

chấp nhận cùng một tập ngôn ngữ ?

Nfa với -dịch chuyển (nfa)

Ta mở rộng mô hình NFA cho phép các phép chuyển trên nhãn rỗng . Sơ đồ chuyển sau đây của một NFA chấp nhận chuỗi gồm một số bất kỳ (có thể là 0) chữ số 0 sau đó là một số bất kỳ chữ số 1 và sau nữa là một số bất kỳ chữ số 2. Thông thường, ta nói NFA chấp nhận một chuỗi w nếu có đường truyền nhãn w từ trạng thái bắt đầu đến một trạng thái kết thúc. Chẳng hạn, chuỗi 002 được chấp nhận bởi đường truyền q0, q0, q0, q1, q2, q2 với các cung nhãn 0, 0, , , 2.

Thí dụ 3.6 : Sơ đồ chuyển của một NFA với -dịch chuyển :

Hình 3.4 - NFA với -dịch chuyển

Định nghĩa: Một cách hình thức ta định nghĩa NFA với -dịch chuyển là bộ 5 thành phần (Q, , , q0, F) với tất cả các thành phần có ý nghĩa như trên, nhưng hàm chuyển  là ánh xạ từ Q  (  {})  2Q.

Khái niệm (q, a) gồm tất cả các trạng thái p sao cho có phép chuyển nhãn a từ q tới p, trong đó a là một ký hiệu thuộc  hoặc là .

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 nhãn w (có thể chứa cạnh nhãn ).

Ta sử dụng -CLOSURE(q) để xác định tập tất cả các đỉnh p sao cho có đường đi từ q tới p với nhãn .

Thí dụ 3.7 : Trong hình 3.4, -CLOSURE(q0) = {q0, q1, q2}.

Vì đường đi chỉ có một đỉnh q0 (không có cung trên đường đi) là đường đi từ q0 tới q0 có tất cả các cạnh nhãn là . Đường đi q0, q1 chỉ ra rằng q1 thuộc -CLOSURE(q0). Và đường đi q0, q1, q2 chỉ ra rằng q2 thuộc -CLOSURE(q0).

Đặt -CLOSURE(P) = qP -CLOSURE(q), trong đó P là một tập các trạng thái và q là một trạng thái. Ta định nghĩa hàm * như sau:

1. *(q, e) = e-CLOSURE(q)

2. *(q, wa) = e-CLOSURE(P),

trong đó tập P = {p  có r trong *(q, w) sao cho p  (r, a)}, w  * và a  

Hay *(q, wa) = e-CLOSURE(d(*(q, w), a)

Ta mở rộng  và * trên tập hợp các trạng thái R như sau :

3.  (R, a) = È qR (q, a), và

4. *(R, w) = ÈqR *(q, w)

Câu hỏi :