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

Chia sẻ: _ _ | Ngày: | Loại File: PPT | Số trang:59

Thêm vào BST

Báo xấu

21
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Chương 2: ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY 1
I. Biểu thức chính quy (BTCQ)  Định nghĩa: Cho bộ chữ  là một BTCQ  ε là một BTCQ  a thì a là một BTCQ  , là các BTCQ( + ), ( . ), ( *) là các BTCQ 2
Biểu thức chính quy …  Quy ước:  Để lược bớt các vòng đơn, áp dụng các mức ưu tiên với các toán tử theo thứ tự *, ., +  Toán tử “*” được viết ở vị trí chỉ số trên.  Toán tử ghép tiếp (.) có thể được bỏ qua: viết β thay vì .β 3
Giá trị của BTCQ  Một BTCQ trên biểu diễn một ngôn ngữ trên  L( )= ; L(ε)= {ε}  L(a)={a} với a  L(( + ))=L( ) L( )  L(( ))=L( ).L( )  L(( *))=(L( ))*  Ta gọi ngôn ngữ chính quy là mọi ngôn ngữ có thể được chỉ định bởi một biểu thức chính quy. 4
Biểu thức chính quy …  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ính chất của BTCQ  Cho r, s, t là các BTCQ: (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ụng các tính chất của biểu thức chính quy rút gọn công thức sau:  ( +0)* + 0  0* +(1+ )(1+ )*(1+ ) 7
Ô tô mát hữu hạn  Ô tô mát hữu hạn:  Trực quan: là máy trừu tượng đoán nhận ngôn ngữ  Hình thức: là hệ viết lại đoán nhận xâu bằng cách viết lại cho đến khi gặp tiên đề.  Gồm hai loại:  Ôtômát hữu hạn tiền định (DFA)  Ôtômát hữu hạn không tiền định(NFA) 8
Cấu tạo của OHT Băng vào 1 0 0 1 1 1 0 Đầu đọc q Cái điều khiển Hình. Ôtômát hữu hạn tiền định 9
Cấu tạo của OHT  Cấu tạo:  Một băng vào: chứa xâu cần xử lý (xâu vào), mỗi ô chứa một kí tự  Một đầu đọc: tại mỗi thời điểm trỏ vào một ô của băng vào và cho phép đọc kí hiệu trong ô đó  Cái điều khiển (bộ chuyển trạng thái): tại mỗi thời điểm có một trạng thái:  Các trạng thái là hữu hạn  Có một trạng thái đầu và các trạng thái thừa nhận  Một hàm dịch chuyển: cho phép xác định trạng thái tiếp theo dựa và trạng thái và kí hiệu đọc được hiện tại 10
Nguyên lý hoạt động  Ban đầu: OHT ở trạng thái đầu, đầu đọc trỏ vào kí hiệu đầu tiên của xâu vào  Lặp:  ÔHT đọc kí hiệu trên băng, xác định trạng thái tiếp theo dựa vào hàm dịch chuyển, đẩy đầu đọc sang phải một ô  OHT dừng khi đọc hết xâu vào, nếu trạng thái cuối là trạng thái thừa nhận thì xâu và được thừa nhận (thuộc ngôn ngữ mà ôtômát mô tả) 11
Định nghĩa OHT  Định nghĩa: OHT là một bộ năm M=( ,Q, ,q0,F) trong đó:  tập hữu hạn các kí hiệu (bộ chữ vào)  Q – tập hữu hạn các trạng thái, Q=  :Q× Q là hàm dịch chuyển  q Q là trạng thái đầu 0  F Q là các trạng thái thừa nhận (trạng thái cuối) 12
Ôtômát hữu hạn tiền định  Ví dụ: Cho ôtômát tiền định M, trong đó: 0 1  Bộ chữ vào ={0,1} q0 q2 q1  Q={q0, q1, q2, q3 }, q0 là q1 q3 q0 trạng thái đầu  F={q0} là tập trạng thái q2 q0 q3 kết thúc q3 q1 q2  Hàm dịch chuyển : Q× Q, cho bởi bảng bên  Xâu vào: 1001 , 11, 0110 13
Ôtômát tiền định  Hệ viết lại ngầm định của ôtômát M là W=(V,P), trong đó:  V= Q  P: tập các sản xuất được xây dựng như sau: Nếu (q,a)=p thì qap là một quy tắc trong P  Ngôn ngữ đoán nhận bởi M là:  L(M)={ | *, q0 *q F} 14
Biểu diễn đồ thị của OHT  Biểu diễn OHT bằng đồ thị:  Mỗi nút biểu diễn một trạng thái, là một vòng tròn có tên trạng thái.  Mỗi cung là một mũi tên chỉ hướng chuyển có kèm kí hiệu gây ra sự chuyển  Nút trạng thái đầu có mũi tên chỉ vào  Nút trạng thái cuối vẽ bằng nét kép 15
Biểu diễn đồ thị của OHT  Ví dụ: M=( ,Q, ,q0,F)  ={0,1}; Q={q0, q1, q2}; F={q1}  được cho bởi: (q0, 0)=q0, (q0, 1)=q1 (q1, 0)=q0, (q1, 1)=q2 (q2, 0)=q2, (q2, 1)=q1 ĐỒ thị chuyển trạng thái tương ứng: 16
Ôtômát hữu hạn không tiền định  Định nghĩa: OHK là bộ 5 M=( ,Q, ,q0,F) trong đó:  bộ chữ vào  Q – tập hữu hạn các trạng thái, Q=  :Q×( {ε}) (Q) là hàm dịch chuyển  q0 Q là trạng thái đầu  F Q là các trạng thái thừa nhận (trạng thái cuối) 17
Ôtômát hữu hạn không tiền định  Ví dụ: Sơ đồ chuyển trạng thái của một OHK 18
Ôtômát hữu hạn không tiền định  OHK khác OHT:  Từ một trạng thái gặp một kí hiệu được đọc vào có thể chuyển sang một số trạng thái tiếp theo (hàm chuyển là hàm đa trị)  Từ một trạng thái có thể không cần kí hiệu vào OHK cũng chuyển trạng thái (dịch chuyển ε) 19
Sự tương đương giữa OHT và OHK  Ta gọi:  L(OHT) là lớp các ngôn ngữ được đoán nhận bởi OHT  L(OHK) là lớp các ngôn ngữ được đoán nhận bởi OHK  Ta chứng minh: L(OHT)=L(OHK) (tức là ngôn ngữ L được đoán nhận bởi OHT  L cũng được đoán nhận bởi một OHK) 20