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

3) r = r*

Đặt M1 (Q1, 1, 1, q1, {f1}) và L(M1) = r1.

Xây dựng M (Q1 {q0, f0} 1, , q0, {f0}), trong đó  được cho:

. d(q0, e) = d(f1, e) = {q1, f0}

. d(q, a) = d1(q, a) với q  Q1 - {f1} và a  1  {}

Cách xây dựng M được chỉ ra trong hình c. Mỗi đường đi từ q0 tới f0 gồm: hoặc đường đi từ q0 tới f0 bằng nhãn ; hoặc đường đi từ q0 tới q1 bằng nhãn  và sau đó là đường đi từ q1 tới f1 trên chuỗi thuộc L(M), rồi đến f0 bằng nhãn . Như vậy có đường đi từ q0 tới f0 nhãn là x nếu và chỉ nếu ta có thể viết x = x1 x2 ... xj với j  0 (trường hợp j = 0 khi x = ) xi  L(M1). Vậy L(M) = L(M1)*.

Thí dụ 3.14 : Xây dựng NFA chấp nhận lớp ngôn ngữ được ký hiệu bởi biểu thức chính quy r = 01* + 1.

Ta thấy L(r) = { 1, 0, 01, 011, 0111, 01111, 011111, … } là tập ngôn ngữ chứa các bit đơn 0, 1 và các chuỗi bit nhị phân bắt đầu bằng bit 0, theo sau là một chuỗi bit 1 với độ dài tuỳ ý.

Theo quy luật thứ tự ưu tiên, biểu thức 01* + 1 thực chất là (0(1*)) + 1, vì vậy nó có dạng r1 + r2 với r1 = 01* và r2 = 1.

Ta sẽ lần lượt xây dựng các NFA cho các biểu thức chính quy con, sau đó dựa vào các quy tắc kết hợp để xây dựng NFA cho toàn bộ biểu thức chính quy đã cho.

. NFA cho r2 = 1 dễ dàng để xây dựng :

. NFA cho r1 = 01*:

Ta tách r1 = r3 r4 , trong đó r3 = 0 và r4 = 1*

+ NFA cho r3 = 0 :

+ NFA r4 = 1* :

Ta viết r4 = r5*, trong đó r5 = 1.

NFA cho r5 = 1 :

Theo quy tắc 3) ta xây dựng được NFA cho r4 = r5* = 1* như sau :

Theo quy tắc 2) ta xây dựng được NFA cho r1 = r3 r4 = 01* như sau :

Cuối cùng, theo quy tắc 1) ta xây dựng NFA cho r = r1 + r2 = 01*+ 1 như sau :

Hình 3.9 - NFAe cho ví dụ 3.13

Phần chứng minh của Định lý 3.3 trên cũng chính là cơ sở của giải thuật chuyển đổi một biểu thức chính quy thành ôtômát hữu hạn. Một điểm cần lưu ý là thứ tự ưu tiên của các phép toán được sử dụng trong biểu thức chính quy, điều này rất quan trọng cho quá trình tách biểu thức chính quy thành các biểu thức con trong những trường hợp viết biểu thức chính quy ở dạng tắt (không có dấu ngoặc).

Bây giờ, ta cần chứng tỏ rằng mọi tập hợp được chấp nhận bởi một ôtômát hữu hạn thì cũng được ký hiệu bởi một số biểu thức chính quy.

ĐỊNH LÝ 3.4 : Nếu L được chấp nhận bởi một DFA, thì L được ký hiệu bởi một biểu thức chính quy.

Chứng minh

Đặt L là tập hợp được chấp nhận bởi DFA M ({q1, q2,..., qn}, , , q1, F).

Đặt Rkij là tập hợp tất cả các chuỗi x sao cho (qi, x) = qj và nếu (qi, y) = ql, với y là tiền tố bất kỳ của x, khác x hoặc , thì l  k. Tức là Rkij là tập hợp tất cả các chuỗi làm cho ôtômát đi từ trạng thái qi tới qj không đi ngang qua trạng thái nào (được đánh số) lớn hơn k. (Chú ý, khái niệm "đi ngang qua một trạng thái" có nghĩa là có phép chuyển vào và ra khỏi trạng thái đó, nên i hoặc j đều có thể lớn hơn k). Vì chỉ có n trạng thái nên Rnij sẽ là tập hợp tất cả các chuỗi làm ôtômát đi từ qi tới qj.

Ta định nghĩa Rkij một cách đệ quy như sau:

Rkij = Rk-1ik (Rk-1kk )* Rk-1kj È Rk-1ij (1)

{ a  (qi, a) = qj } nếu i  j

R0ij =

{ a  (qi, a) = qj }  {} nếu i = j

Một cách hình thức, Rkij định nghĩa như trên là các chuỗi nhập hay nguyên nhân đưa M từ qi tới qj không đi ngang qua trạng thái cao hơn qk, nghĩa là xảy ra hoặc một trong hai trường hợp sau :