Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 3

Nội dung

Chương 3:

VĂN PHẠM CHÍNH QUY VÀ ÔTÔMÁT HỮU HẠN

1. Ôtômát hữu hạn đơn định - DFA. 2. Ôtômát hữu hạn không đơn định - NFA. 3. Sự tương đương của NFA và DFA 4. Mối liên quan giữa VPCQ và OH 5. OHD không xuất phát lại 6. Các tính chất đóng của ngôn ngữ chính quy. 7. Định lý KLEENE. 8. Biểu thức chính quy. 9. Thuật toán Thampson

Ôtômát hữu hạn đơn định – DFA (Deterministic Finite Automata)

Input : w  *

Băng từ sức chứa vô hạn

Bộ điều khiển

 Mô tả phi hình thức:  Ôtômát hữu hạn như một “máy” đoán nhận chuỗi, nó

 Có một đầu đọc, ở mỗi thời điểm quan sát một ô trên

Output : Yes, w  L No, w  L làm việc như sau:  Băng từ chia thành nhiều ô. Mỗi ô có khả năng lưu trữ một ký hiệu của chuỗi nhập (chuỗi cần được đoán nhận w є *).

băng từ.  Tùy theo cấu hình hiện tại gồm (trạng thái hiện thời của bộ điều khiển và ký hiệu trên ô mà đầu đọc quan sát được), mà Ôtômát chuyển sang trạng thái mới, đồng thời đầu đọc dịch chuyển sang phải một ô.  Quy luật chuyển sang trạng thái mới, được cho bởi một hàm, gọi là hàm chuyển trạng thái : Q x   Q.  Có một bộ điều khiển Q gồm tập hợp hữu hạn trạng thái; ở mỗi thời điểm có một trạng thái hiện hành gọi là trạng thái nội.

1

 Trong Q có phân biệt q0  Q, gọi là trạng thái đầu và một tập hợp F chứa các trạng thái kết thúc.  Định nghĩa hình thức: Một ôtômát hữu hạn đơn định (viết tắt là

 Ta nói ôtômát đoán nhận (hay thừa nhận) một chuỗi vào w  *, nếu xuất phát từ q0, đầu đọc nhìn vào ký hiệu bên trái nhất của w, sau một số bước hữu hạn làm việc, nó đọc xong chuỗi w và rơi vào một trong các trạng thái kết thúc.  Tập hợp mọi chuỗi (được đoán nhận bởi Ôtômát) hợp thành ngôn ngữ được đoán nhận bởi ôtômát đó.

ÔHĐ) là một hệ thống M = (, Q, , q0, F) trong đó:   là một bộ chữ cái hữu hạn, gọi là bộ chữ vào.  Q là một tập hữu hạn các trạng thái,   Q = .  : Q x   Q, được gọi là hàm chuyển.  q0  Q là trạng thái đầu.  F  Q là tập các trạng thái cuối.

 Do Q là hữu hạn và hàm chuyển  là hàm toàn phần và đơn trị, cho nên bước chuyển của Ôtômát được xác định một cách duy nhất. Chính vì vậy mà Ôtômát mô tả như trên được gọi là ôtômát hữu hạn đơn định.

Biểu diễn hàm chuyển trạng

 Ví dụ 3.1: Xét Ôtômát hữu hạn đơn định M(,Q, ,q0,F). trong đó:

 Có 3 cách biểu diễn hàm chuyển (hàm chuyển trạng thái):

 = {0, 1}

F = {q0}

Q = {q0, q1, q2, q3} Hàm  cho bởi ma trận sau:

Ký hiệu vào

Trạng thái

 Theo định nghĩa  (qi,a)=qj  Theo bảng truyền  Theo đồ thị

2

Đầu

Bắt đầu

 Biểu đồ chuyển cho Ôtômát hữu hạn nói ở trên (Ví dụ 3.1) sẽ như sau:

 Để cho dễ hình dung hơn, ta thường biểu diễn hàm chuyển dưới dạng một đồ thị định hướng, gọi là biểu đồ chuyển như sau:  Mỗi nút tương ứng với một trạng thái.  Nút đầu trỏ bởi mũi tên có chữ “Bắt đầu”.  Nút cuối được khoanh bởi hai vòng tròn.  Nếu (q, a) = p thì có một cung đi từ nút q tới nút p, và cung đó mang nhãn a.

Tính chất của hàm chuyển trạng

Định nghĩa tập đoán nhận bởi (M)

 Ký hiệu T(M)  T(M) = { w | w  * , (q0,w) = qf  F }  Ví dụ:

1.  (q,)=q 2.  (q,wa)=  ((q,w),a) 3.  (q,aw)=  ((q,a),w), w  * và a   4.  (q,xy)=  ((q,x),y), x,y  *  w1 = 1010  w2 = 11001001  W3 = 110101

3 Quá trình đoán nhận chuỗi vào

 Ta gọi một hình trạng của ÔHĐ là một chuỗi có dạng qx

110101 110101 110101 110101 110101 110101

q0  F

 VD: q0w3 = q0 110101 là một hình trạng của (M)  Quá trình đoán nhận một chuỗi của ÔHĐ là quá trình biến đổi các hình trạng, thực chất là quá trình “viết lại” chuỗi.

 Cho chuỗi w= 110101. Quá trình đoán nhận chuỗi vào đó diễn tả bằng các bước chuyển sau: với q  Q và x  *.

 VD: Viết quá trình đoán nhận chuỗi x = 110101

 Vì q0F, vậy chuỗi vào w=110101 được thừa nhận bởi Ôtômat.  Nhận xét rằng mỗi trạng thái của M ghi nhớ một tình trạng nhất

định của phần chuỗi vào đã đọc như sau:  q0: phần đã đọc chứa một số chẵn con số 0 và một số chẵn con số 1.  q1: phần đã đọc chứa một số chẵn con số 0 và một số lẻ con số 1.

Ngôn ngữ đoán nhận (thừa nhận) bởi M

Tập các chuỗi được ôtômát thừa nhận

 q2: phần đã đọc chứa một số lẻ con số 0 và một

số chẵn con số 1.

 q3: phần đã đọc chứa một số lẻ con số 0 và một

số lẻ con số 1.

q00  q2

q10  q3

q20  q0

q30  q1

 Mỗi lần đọc thêm một ký hiệu 0 hay 1, hàm  luôn

q01  q1

q11  q0

q21  q3

q31  q2

L(M) = {w| w  * và q0w * p với p  F}  Ngôn ngữ đoán nhận (hay thừa nhận) bởi M là:  Trở lại ví dụ 3.1, hệ viết lại ngầm định của nó gồm các sản xuất sau:

luôn chuyển trạng thái của ôtômát về đúng tình trạng trên. Vì F = {q0}, cho nên các chuỗi được M thừa nhận là các chuỗi có chứa một số chẵn con số 0 và một số chẵn con số 1.

= q0  F

 Quá trình đoán nhận chuỗi w = 110101 là: q0110101  q110101  q00101  q2101  q301  q11  q0  F  Có một cách viết khác (thường thấy ở các sách khác): (q0,110101)=(q1,10101)=(q0,0101)=(q2,101)=(q3,01)= (q1, 1)

4 Ôtômát hữu hạn không đơn định (tt)

Ôtômát hữu hạn không đơn định – NFA (Nondeterministic Finite Automata)

 Dễ dàng mở rộng mô hình ÔHĐ trên để cho hệ viết lại ngầm

định của Ôtômát là một hệ viết lại không đơn định, tức là có thể chứa các sản xuất có cùng vế trái.  Định nghĩa: Ta gọi Ôtômát hữu hạn không đơn định (hay không

 Tập đoán nhận bởi Ôtômat T(M) = {w | w  * và q0w * qf với qf  F}.  Ngôn ngữ đoán nhận bởi M là: L(M) = {w | w  * và q0w  * qf với qf  F}.  Chuỗi vào w được (M) thừa nhận nếu tồn tại ít nhất một quá trình dẫn xuất q0w  * qf với qf  F.

 Ví dụ 3.2: Xét ÔHK M = ({0,1}, {q0, q1, q2, q3, q4}, , q0, {q2, q4}) với hàm chuyển  cho như sau:

M = {, Q, , q0, F} Trong đó: , Q, q0, F vẫn như tương tự OHĐ. Chỉ duy tiền định) viết tắt là ÔHK, là một hệ thống: nhất hàm  là đổi lại: : Q x   2Q.  Hệ viết lại W = (V, P) ngầm định của M cũng có V =   Q.

Ôtômát hữu hạn không đơn định (tt)

0, 1



0, 1

 Nếu xét tất cả các quá trình, ta có một “cây” như sau:

{q0, q3}

{q0, q1}

Đầu

q001001

 q01001  q0001  q001  q01  q0



{q2}

q0 1

q31001

q1001

q301

q31

{q2}



{q4}

q1 1

q41  q4  F

0, 1

{q4}

 Sau đây là quá trình đoán nhận chuỗi vào 01001, dẫn tới trạng thái cuối q4:  Như vậy chuỗi 01001 đã thừa nhận bởi M.  Dễ thấy rằng ÔHK này thừa nhận các chuỗi trên {0, 1} có chứa hai con 0 liên tiếp hoặc có chứa hai con 1 liên tiếp.  L (M) = { w00w, w11w | w  * ={0,1}*} q001001  q01001  q0001  q301  q41  q4  F  Đây chỉ là một quá trình đoán nhận trong nhiều quá trình.

5 Sự tương đương giữa ÔHĐ và ÔHK

Sự tương đương giữa ÔHĐ và ÔHK (tt)

 B2: Hàm chuyển ’ của M’ được thành lập theo công thức:

• Mỗi phần tử trong Q’ được ký hiệu bởi tập hợp {q1, q2, …, qk}, với q1, q2, …, q0  Q. L(ÔHĐ)  L(ÔHK) (1)  Theo định nghĩa mỗi ÔHĐ cũng là một ÔHK, cho nên:  Định lý 3.1: Nếu L một ngôn ngữ được đoán nhận bởi một • Trạng thái đầu q0’ = {q0}. ÔHK, thì cũng có một ÔHĐ đoán nhận L.

(qi , a) ’({q1, q2, …, qk}, a) =

 B3: Vẽ đồ thị chuyển trạng thái

 B4: Kết luận M’ và chú thích rõ 5 phần của Ôtômát

 Với cách thành lập M’ trên ta hoàn toàn CM được L(M) = L(M’) (Tham khảo

Nói cách khác L(ÔHK)  L(ÔHĐ) (2)  Giải thuật: Input: M = (, Q, , q0, F) là ÔHK đoán nhận L. Output: M’ = (, Q’, ’, q0’, F’) là OHĐ sao cho L(M’)=L(M)  B1: Đặt M’ = (, Q’, ’, q0’, F’), trong đó:

sách “Ngôn ngữ hình thức” – Nguyễn Văn Ba, trang 32).

• Q’ = 2Q • F’ là tập mọi trạng thái trong Q’ có chứa một trạng thái cuối nào đó của M.

Sự tương đương giữa ÔHĐ và ÔHK (tt)

 Ví dụ 3.3: Cho M = ({0, 1}, {q0, q1, q2}, , q0, {q2}), là một ÔHK trong đó hàm chuyển trạng thái như sau:

(q0, 0) = {q0, q1}

(q0, 1) = {q1}

(q1, 0) = {q2}

(q1, 1) = 

(q2, 0) = {q2}

(q2, 1) = {q2}

Tìm OHĐ tương đương?

• Kết luận : M’ =( , Q’, ’, {q0}, F’) là OHĐ cần tìm. Trong đó:  = Q’ = ’ (vẽ đồ thị Chú ý: cắt bỏ các nhánh không xuất phát từ q0 hoặc xuất phát từ q0 nhưng không kết thúc được) q0 là trạng thái bắt đầu F’ =

6 Sự tương đương giữa ÔHĐ và ÔHK (tt)

Bổ đề 3.1:  Lớp các ngôn ngữ đoán nhận bởi Ôtômát hữu hạn đơn định (hay không đơn định) là một, và gọi là lớp các ngôn ngữ chính quy (viết tắt là NNCQ).

 NNCQ được sinh ra bởi VPCQ nên VPCQ có

 Thực ra trong 2Q thường có nhiều phần tử không thể truy đạt từ {q0}, nên chẳng cần đưa chúng vào Q’. Vậy để lập Q’, ta nên truy xuất từ {q0}, rồi từng bước thêm dần các trạng thái mới, nếu các trạng thái này là kết quả của hàm chuyển thái áp dụng lên các trạng thái đã có trước đó.

mối quan hệ mật thiết với OH. Nghĩa là L(G)=L(M)=L là NNCQ

 Định lý 3.2: Nếu L là một NNCQ trên bộ chữ cái , thì tồn tại một VPCQ phải G sao cho L –

 Định nghĩa VPCQ (nhắc lại):

Cho ôtômát hữu hạn đơn định xây dựng VPCQ Văn phạm chính quy

A  wB | w, với w  * và A, B  .

• Một văn phạm chính quy phải nếu tập luật sinh của nó dạng:

Output

Input

G = (T, V, P, S)

M = (, Q, , q0, F)

{} = L(G).  Giải thuật: (xây xựng một VPCQ phải từ một ôtômát hữu hạn đơn định)  Input: L = L(M) với M = (, Q, , q0, F) là ÔHĐ.  Output:Ta thành lập văn phạm G = (T, V, P, S) sao cho L(G)=L \ {}

T = 



V = {V0,V1,V2,…} P= V0  aV1 V1  aVf | a a  T

Q = {q0, q1, q2,….}  (q0, a) = q1 (q1, a) = qf  F a   và q0,q1  Q

S là kí hiệu bắt đầu trong P

q0 F  Q

A  Bw |w, với w  * và A, B  . • Một văn phạm chính quy trái nếu tập luật sinh của nó dạng: • Các văn phạm chính quy phải và trái được gọi chung là văn phạm chính quy (viết tắt là VPCQ). • Ngôn ngữ được sinh ra bởi VPCQ gọi là NNCQ.

7

GIẢI

Start

Ví dụ 3.4: Tìm văn phạm chính qui sinh ra ngôn ngữ L. Biết rằng L là ngôn ngữ được đoán nhận bởi OH sau đây:  Văn phạm sinh ra ngôn ngữ L có dạng M=(, Q,,q1,F)

 xác định như đồ thị: ={a,b,c} Q={q1,q2,q3} F={q3} q1 là trạng thái bắt đầu

G=(T,V,P,S) T={a,b,c} V={S,A,B,} P={S  aS | aA A  bA | bB | b B  cB | c} S là kí hiệu bắt đầu trong tập luật sinh



Đầu

a,b

Biểu đồ chuyển của ÔHĐ

 Ví dụ 3.5: Cho ÔHĐ M với  = {a, b}, Q = {q0, q1, q2, q3}, F = {q2}. Hàm chuyển  cho như sau:

L(M) = {ambn | m, n > 0}

Tìm văn phạm G sinh ra ngôn ngữ L, sao cho L=L(M) Tìm L? (Có chứng minh) Ngôn ngữ tìm được là ngôn ngữ gì?  Tìm một số quá trình đoán nhận của OH: Xét w1 = aabbb q0aabbb  q1abbb  q1bbb  q2bb  q2b  q2  F  w1  L(M) Xét w2 = aaa q0aaa  q1aa  q1a  q1 F  w2  L(M) Xét w3 = ba, thật vậy: q0ba  q3a  q3 F  w3  L(M) Xét w4 = aba,thật vậy:q0aba  q1ba  q2a  q3  F  w4  L(M)  w2, w3, w4  L(G) (theo bổ đề 3.1)  T(M)={ab,aab,aabbb,abb,aaab,abbbb,…}  Dễ thấy rằng ngôn ngữ do Ôtômát M đoán nhận là: • Tìm văn phạm G sinh ra ngôn ngữ L, sao cho L(G)=L(M) • SV tự làm!

8

Cho VPCQ xây dựng ôtômát hữu hạn không đơn định Cho VPCQ xây dựng ôtômát hữu hạn không đơn định  Cách xây dựng hàm chuyển trạng thái 

Input

Output

G = (T, V, P, S)

M = (, Q, , q0, F)

 =T

 Định lý 3.3: Nếu G là một VPCQ phải, thì L(G) là một ngôn ngữ chính quy.  Giải

Start

thuật xây dựng một ôtômát hữu hạn không đơn định từ một VPCQ phải:

 Mỗi sản xuất dạng Vi  a1a2 … anVj thuộc P Ta có hàm chuyển trạng (qi, a1a2a3…an) = qj Đồ thị vẽ như sau:

….

V = {V0,V1,V2…} Q = {q0, q1, q2,…} P= {V0  aV1 V1  a1a2a3…V2 V2  a}

 Input: G = (T, V, P, S).  Output:Ta

 (q0,a) = q1 (q1, a1a2a3…) = q2 (q2,a) = q3

q0 là trạng thái bắt đầu

lập một thành ÔHK M đoán nhận L(G) như sau:

V0 là kí hiệu bắt đầu trong P

M = (, Q, , q0, F)

F = {q3 }  Q Vẽ đồ thị

Start

Kết luận M?

 Mỗi sản xuất dạng Vi  a1a2 … an thuộc P Ta có hàm chuyển trạng (qi, a1a2a3…an) = qf  F Đồ thị vẽ như sau:

….

 Ví dụ 3.6: Xây dựng một Ôtômát hữu hạn chấp nhận ngôn ngữ được sinh bởi văn phạm có tập luật sinh như sau:

S  aA A  abS| b

Start

 (q0,a)=q1  (q1,ab)=q0  (q1,b)=q2  F  F = {q2}  q0 là trạng thái bắt đầu  Vẽ đồ thị chuyển trạng thái như sau:

Giải Đặt M=(,Q, , q0,F) là OH cần tìm Trong đó: ={a,b} Q={q0,q1}  Xác định như sau:

9

Kết luận M=(,Q, , q0,F) là OH cần tìm

ÔHĐ không xuất phát lại

•Định nghĩa: Một ÔHĐ là không xuất phát lại nếu không tồn tại cặp (q, a) để cho (q, a) = q0 với q0 là trạng thái đầu

•Bổ đề 3.2: Có giải thuật cho phép biến đổi một ÔHĐ M đã cho thành một ÔHĐ không xuất phát lại M’ sao cho L(M’) = L(M).

Start

 Xác định như sau:

Giải thuật: –Giả sử M = (, {q0, q1, …, qn}, , q0, F). –Lập ÔHĐ M’ = (, Q  {qn+1}, ’, q0, F’) trong đó:

• Trong đó: • ={a,b} • Q={q0,q1,q2,q3} • • F = {q2} • q0 là trạng thái bắt đầu

ÔHĐ không xuất phát lại

Nếu q  Q và (q, a)  q0

Nếu q  Q và (q, a) = q0

 Ví dụ 3.7: Tìm OHĐ không xuất phát lại M’ tương đương với OHĐ có xuất phát lại M sao cho L(M’)=L(M)

(M)

’(qn+1, a) = ’(q0, a)

Nếu q0 không thuộc F

Nếu q0  F

Gợi ý OHĐ không xuất phát lại cần tìm sẽ có đồ thị chuyển trạng thái sau: Kết luận M' (, Q  {qn+1}, ’, q0, F’) , chú thích 5 phần?

(M’)

Dễ thấy M’ thực hiện cùng các bước chuyển như M, trừ khi M chuyển về q0 thì M’ chuyển sang qn+1, nhưng sau đó lại tiếp tục bắt chước như M thường.

10 Các tính chất đóng của lớp các NNCQ (tt)

a

b

’



 Định lý 3.7: Nếu L và L’ đều là các NNCQ thì LL’ cũng là

 Định lý 3.4: Nếu L và L’ là các NNCQ thì L  L’ cũng là NNCQ.  Định lý 3.5: Nếu L  * là một NNCQ, thì * - L cũng là NNCQ.  Định lý 3.6: Nếu L và L’ là các NNCQ thì L  L’ cũng là NNCQ. Bổ đề 3.3: Cho L  * và   ’. Có một ÔH với bộ chữ vào  đoán nhận L khi và chỉ khi có một ÔH với bộ chữ vào ’ đoán nhận L. (Nói cách khác khái niệm NNCQ không tùy thuộc vào bộ chữ).

 Gọi M’=(, Q  {qn+1}, ’, q0, F’) là OHĐ cần tìm  Trong đó:   = {a,b}  Q = {q0, q1,q2,q3 }  F’ = {q0,q2,q3}  q0 là trạng thái bắt đầu  ’ như đồ thị NNCQ.  Định lý 3.8: Nếu L là NNCQ thì L* cũng là NNCQ.

BIỂU THỨC CHÍNH QUI

Định lý KLEENE

 Cách khác để mô tả ngôn ngữ chính qui là dùng biểu

thức chính qui (BTCQ).  Một BTCQ là sự kết hợp:  Các ký tự trong , mỗi ký tự có thể xuất hiện nhiều lần,

 Định lý KLEENE: Mọi NNCQ đều có thể nhận được từ các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu hạn lần các phép hợp, ghép tiếp và *.

 Các toán tử: bao đóng (+,*), ghép, hợp  Các dấu ngoặc: ()  Định lý:  và {} là các NNCQ.  Định lý: Với mọi w  *, thì {w} là NNCQ.  Hệ quả: Mọi tập con hữu hạn của * đều là NNCQ.  Hệ quả: Mọi ngôn ngữ tạo nên từ các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu hạn lần các phép hợp, ghép tiếp và * đều là NNCQ.

 VD:  Với ngôn ngữ L= {a}, ta có BTCQ là a  L={a,b}, ta có BTCQ là a+b  L={ab}  {a}, ta có BTCQ là ab+a  L={a,b} . {a} , ta có BTCQ là (a+b)a

11 Biểu thức chính qui

Biểu thức chính qui (tt)

 Các toán tử ưu tiên trong BTCQ từ cao tới thấp:

(1) Bao đóng :

0+ : số 0 được lặp lại ít nhất 1 lần, nhiều nhất n lần. 0* : số 0 được lặp lại ít nhất 0 lần, nhiều nhất n lần

(2) Ghép : . (3) Hợp : + Khi viết một BTCQ, ta có thể bỏ qua một số ngoặc đơn, chẳng hạn, ((0(1*))+0) có thể viết thành 01* + 0 vẫn dễ hiểu.

 Ta cũng có thể viết tắt biểu thức rr* bởi r+.

 Định nghĩa 1: Cho  là một bộ chữ. Một biểu thức chính quy (viết tắt là BTCQ) trên  và tập hợp do nó định nghĩa được chỉ định được định nghĩa một cách đệ quy như sau: 1. Các biểu thức chính qui nguyên tố gồm:  là một biểu thức chính quy biểu thị tập rỗng.  là một biểu thức chính quy biểu thị tập {}.  a   thì a là một biểu thức chính quy biểu thị tập {a}. 2. Nếu r và s là các biểu thức chính quy, lần lượt chỉ định các tập R và S, thì (r+s), (rs), và (r*) là các biểu thức chính quy, và lần lượt biểu thị các tập R  S, RS, và R*. 3. Một BTCQ nếu và chỉ nếu nó có thể được xây dựng từ các biểu thức chính qui nguyên tố bởi áp dụng một số hữu hạn lần các qui tắc trong mục 2.

Biểu thức chính qui (tt)

 Liên kết giữa ngôn ngữ với BTCQ Tập hợp các chuỗi được chỉ định bởi một BTCQ r được ký hiệu bởi L(r). Để cho tiện ta dùng r vừa để chỉ biểu thức chính quy, vừa để chỉ tập hợp do nó chỉ định.

Biểu thức chính qui (tt)  00 là một biểu thức chính quy chỉ định tập L={00}  (0+1)* chỉ định tập mọi chuỗi 0 và 1  (1+10)* chỉ định tập mọi chuỗi 0 và 1, có con 1 ở đầu và không

 Định nghĩa 2: Ngôn ngữ L(r) được biểu thị bởi bất kỳ một BTCQ r nào, thì được định nghĩa

có hai con 0 liên tiếp.  (0+)(1+10)* chỉ định tập mọi chuỗi 0 và 1 không chứa hai con 0 liên tiếp. Cách khác (1+01)*(0+ )

bởi các qui tắc sau: 1.  là một biểu thức chính qui biểu thị tập rỗng. 2.  là một biểu thức chính qui biểu thị tập {}. 3.  a   thì r = a là một biểu thức chính qui biểu thị tập L(r) = {a}.

 Nếu r và s là các BTCQ thì: 4. L(r+s) = L (r)  L(s) 5. L(r.s) = L(r) L(s) 6. L((r)) = L(r) 7. L(r*) = (L(r))*

 (0+1)*011 chỉ định tập mọi chuỗi 0, 1 kết thúc bởi 011.  0*1*2* chỉ định tập mọi chuỗi gồm một số con 0, tiếp đến một số con 1, rồi đến một số con 2.  00*11*22* chỉ định tập các chuỗi trong đó 0, 1, 2 đều có mặt. Biểu thức đó thường được viết tắt là 0+1+2+.  Ví dụ 3.8: Hãy xây dựng BTCQ xác định các chuỗi có chứa số 0 và 1 xen kẻ nhau.

12 Biểu thức chính qui (tt)

 Các tính chất đại số của biểu thức chính qui:

Dễ dàng Giải thuật rằng, cho r, s, t là các biểu thức chính quy, thì ta có các đẳng thức sau, trong đó r = s có nghĩa là L(r) = L(s).

 Ví dụ 3.8: cho BTCQ r = a* . (a+b)  Tìm ngôn ngữ L(r) gồm tất cả các chuỗi được chỉ định 1. r + s = s + r 8. r = r =  bởi r. 2. r + r = r 9. r +  = r Giải 3. r + (s + t) = (r + s) + t 10. * =  4. r(st) = (rs)t 11. (+r)* = r* 5. r(s + t) = rs + rt 12. r + r* = r*  Ta có L(r) = L(a*. (a+b)) = L(a*) L(a+b)  = (L(a))* (L(a)  L(b))  = {an | n  0} {a,b}  = {an+1, anb | n  0 } 6. (r + s)t = rt + st 13. (r*)* = r* 7. r = r =r 14. (r*s*)* = (r + s)*.

Biểu thức chính qui (tt)

Liên quan giữa BTCQ và OH

 Ví dụ 3.9: Cho BTCQ r = (aa)* (bb)*b

Biểu thị cho tập hợp tất cả các chuỗi sao cho có chẳn con chữ a theo sau là lẻ con chữ b. Đó là L(r) = {a2n b2m+1 | n,m  0 }

BTCQ mà tập nó chỉ định là L.

 Ví dụ 3.10: Cho  = {0,1}. Hãy xác định BTCQ r sao cho L(r) = {w  * |

 Bổ đề 3.4: Với mọi tập hữu hạn L  *, đều tồn tại một một

w có ít nhất một cặp số 0 liên tiếp } Phân tích: mỗi chuỗi w chứa tổi thiểu 00, trước và sau nó là tùy ý 0, 1 điều được. Ta đã biết một chuỗi tùy ý trên  = {0,1} được biểu thị bởi BTCQ là (0+1)* hoặc (1+0)* điều đúng. Vậy BTCQ cần tìm là r = (0+1)*00(1+0)*

Ghi chú: Thông thường có vô số các BTCQ cho bất lỳ một ngôn ngữ nào.

Nên kết quả tìm BTCQ không phải là duy nhất.

 Định lý 3.9: Một ngôn ngữ L được chỉ định bởi một BTCQ khi và chỉ khi nó được đoán nhận bởi một Ôtômát hữu hạn.

13 Thuật toán Thompson

Thuật toán Thompson (tt)

 Sau đó áp dụng luật 1, luật 2 để xây dựng các ôtômát

Đầu

không đơn định M1, M2,…, Mk tương đương đoán nhận các ngôn ngữ L(r1), L(r2), …, L(rk).  Bài toán: Cho một biểu thức chính quy. Hãy xây dựng ôtômát hữu hạn không đơn định đoán nhận ngôn ngữ chính quy từ biểu thức chính quy đã cho.  Thuật toán:  Cuối cùng áp dụng luật 3 để xây dựng ôtômát không đơn định M đoán nhận ngôn ngữ L(r).  Vào: Một biểu thức chính quy r trên tập .  Ra: Một ôtômát hữu hạn không đơn định đoán nhận ngôn ngữ L(r). • Luật 1: BTCQ r=, ngôn ngữ biểu thị cho nó là L(r) = {}. Xây dựng OH đoán nhận L(r) như sau:  Sau đây là thuật toán Thompson:  Trước hết tách biểu thức chính quy r thành các biểu thức  chính quy thành phần r1, r2,…rk.

Thuật toán Thompson (tt)

M(r)

Đầu

M(s)

Đầu

  • Luật 2: BTCQ r=a trên  ={a}, ngôn ngữ do nó sinh ra là L(r)= {a}. Xây dựng OH đoán nhận L(r) như sau:  

• Luật 3: Giả sử M(r), M(s) là các ôtômát thành

a b. Đối với BTCQ (r).(s) thì OHK đoán nhận ngôn ngữ L(r).L(s) như sau:

Đầu

M(r)

M(s)

phần tương ứng với các BTCQ s và r:

a. Với BTCQ (r)  (s) ta xây dựng OH đoán nhận ngôn ngữ L(r)  L(s) như sau:

14 Thuật toán Thompson (tt)

Bài tập: cho NNCQ xây dựng Ôtômát

M(r)

Đầu

c. Đối với BTCQ (r)* thì OHK đoán nhận ngôn ngữ (L(r))* như sau: 



 

 Ví dụ 3.12: Xây dựng Ôtômát đoán nhận tất cả các chuỗi trên  = {a,b,0,1} sao cho kết thúc bởi ab  Ví dụ 3.13: Xây dựng Ôtômát đoán nhận tất cả các chuỗi thuộc {0, 1}* sao cho có chứa chuỗi con 01 đâu đó.  Ví dụ 3.14: Xây dựng Ôtômát đoán nhận ngôn ngữ L={aabna | n 0}  Ví dụ 3.11: Xây dựng NFA từ biểu thức chính quy: 01*+1