Bài giảng Ngôn ngữ hình thức: Chương 2 - Nguyễn Thị Hồng

Bài giảng Ngôn ngữ hình thức: Chương 2 Ôtômát hữu hạn và biểu thức chính quy, cung cấp cho người học những kiến thức như: Biểu thức chính quy; Nguyên lý hoạt động Ôtômát; Ôtômát hữu hạn tiền định; Sự tương đương giữa ô tô mát hữu hạn và biểu thức chính quy. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Ngôn ngữ hình thức: Chương 2 - Nguyễn Thị Hồng Chương2:ÔTÔMÁTHỮUHẠNVÀBIỂU THỨCCHÍNHQUY 1 I.Biểuthứcchínhquy(BTCQ) Địnhnghĩa:Chobộchữ  làmộtBTCQ  εlàmộtBTCQ  a thìalàmộtBTCQ  , làcácBTCQ( + ),( . ),( *)làcácBTCQ 2 Biểuthứcchínhquy… Quyước:  Đểlượcbớtcácvòngđơn,ápdụngcácmứcưu tiênvớicáctoántửtheothứtự*,.,+  Toántử“*”đượcviếtởvịtríchỉsốtrên.  Toántửghéptiếp(.)cóthểđượcbỏqua:viết βthayvì .β 3 GiátrịcủaBTCQ MộtBTCQtrên biểudiễnmộtngônngữtrên  L( )= ;L(ε)={ε}  L(a)={a}với a  L(( + ))=L( ) L( )  L(( ))=L( ).L( )  L(( *))=(L( ))* Tagọingônngữchínhquylàmọingônngữcóthể đượcchỉđịnhbởimộtbiểuthứcchínhquy. 4Biểuthứcchínhquy… Vídụ: ={0,1} BTCQ Giá trị 00 {00} (0+1)* {0,1}* (0+1)*00(0+1)* {x|x {0,1}* và x chứa 2 con 0 liên tiếp} (1+10)* {x|x {0,1}* x có con 1 ở đầu và không có hai con 0 liên tiếp} 5 TínhchấtcủaBTCQ Chor,s,tlàcácBTCQ: (1)r+s=s+r (8)r+r=r (2)r+(s+t)=(r+s)+t (9)r(st)=(rs)t (3)r(s+t)=rs+rt (10)(r+s)t=rt+st (4)rε=εr=r (11) r=r = (5)r+ =r (12) *=ε (6)(ε+r)*=r* (13)r+r*=r* (7)(r*)*=r* (14)(r*s*)*=(r+s)* 6 Vídụ Sửdụngcáctínhchấtcủabiểuthứcchính quyrútgọncôngthứcsau:  ( +0)*+0  0*+(1+ )(1+ )*(1+ ) 7Ôtômáthữuhạn Ôtômáthữuhạn:  Trựcquan:làmáytrừutượngđoánnhậnngôn ngữ  Hìnhthức:làhệviếtlạiđoánnhậnxâubằng cáchviếtlạichođếnkhigặptiênđề. Gồmhailoại:  Ôtômáthữuhạntiềnđịnh(DFA)  Ôtômáthữuhạnkhôngtiềnđịnh(NFA) 8CấutạocủaOHT Băngvào 1 0 0 1 1 1 0 Đầuđọc q Cáiđiềukhiển Hình.Ôtômáthữuhạntiền định 9 CấutạocủaOHT Cấutạo:  Mộtbăngvào:chứaxâucầnxửlý(xâuvào),mỗiôchứa mộtkítự  Mộtđầuđọc:tạimỗithờiđiểmtrỏvàomộtôcủabăng vàovàchophépđọckíhiệutrongôđó  Cáiđiềukhiển(bộchuyểntrạngthái):tạimỗithờiđiểm cómộttrạngthái:  Cáctrạngtháilàhữuhạn  Cómộttrạngtháiđầuvàcáctrạngtháithừanhận  Mộthàmdịchchuyển:chophépxácđịnhtrạngtháitiếp theodựavàtrạngtháivàkíhiệuđọcđượchiệntại 10 Nguyênlýhoạtđộng Banđầu:OHTởtrạngtháiđầu,đầuđọctrỏvàokíhiệuđầu tiêncủaxâuvào Lặp:  ÔHTđọckíhiệutrênbăng,xácđịnhtrạngtháitiếptheo dựavàohàmdịchchuyển,đẩyđầuđọcsangphảimộtô  OHTdừngkhiđọchếtxâuvào,nếutrạngtháicuốilà trạngtháithừanhậnthìxâuvàđượcthừanhận(thuộc ngônngữmàôtômátmôtả) 11 ĐịnhnghĩaOHT Địnhnghĩa:OHTlàmộtbộnămM=( ,Q, ,q0,F) trongđó:  tậphữuhạncáckíhiệu(bộchữvào)  Q–tậphữuhạncáctrạngthái, Q=  :Q× Qlàhàmdịchchuyển  q Qlàtrạngtháiđầu 0  F Qlàcáctrạngtháithừanhận(trạngtháicuối) 12 Ôtômáthữuhạntiềnđịnh Vídụ:Choôtômáttiền địnhM,trongđó: 0 1  Bộchữvào ={0,1} q0 q2 q1  Q={q0,q1,q2,q3},q0là q1 q3 q0 trạngtháiđầu  F={q0}làtậptrạngthái q2 q0 q3 kếtthúc q3 q1 q2  Hàmdịchchuyển :Q× Q,chobởibảngbên  Xâuvào:1001,11,0110 13 Ôtômáttiềnđịnh HệviếtlạingầmđịnhcủaôtômátMlàW=(V,P), trongđó:  V= Q ...