tailieunhanh - Chương 3 - Ngôn ngữ chính quy và văn phạm chính quy

Regular Expressions Alphabet S 1. Æ, l và a Î å là các bi u th c chính quy. Nh ng bi u th ể ứ ữ ể ức này gọi là các biểu thức chính qui nguyên tố. 1. Nếu r1 và r2 là các biểu thức chính quy thì r1 + r2, r1 . r2, r1* và (r1) cũng là các biểu thức chính quy. 2. Một chuỗi gọi là biểu thức chính quy nếu và chỉ nếu nó có thể được xây dựng từ các biểu thức chính quy nguyên tố bởi áp dụng một số hữu hạn lần các quy tắc trong mục 2 | NGÔN NGỮ CHÍNH QUY VÀ VĂN PHẠM CHÍNH QUY Dr. Huỳnh Trung Hiếu Faculty of Information Technology HoChiMinh City University of Industry Regular Languages & Grammars L is regular iff L = L(M) for some DFA M Trong chương này, ta sẽ nghiên cứu những cách khác để biểu diễn ngôn ngữ chính quy. Regular Languages & Grammars Way of representing Way of thinking Regular Expressions L = value of E Regular Expressions Alphabet , và a là các biểu thức chính quy. Những biểu thức này gọi là các biểu thức chính qui nguyên tố. Nếu r1 và r2 là các biểu thức chính quy thì r1 + r2, r1 . r2, r1* và (r1) cũng là các biểu thức chính quy. Một chuỗi gọi là biểu thức chính quy nếu và chỉ nếu nó có thể được xây dựng từ các biểu thức chính quy nguyên tố bởi áp dụng một số hữu hạn lần các quy tắc trong mục 2. Ngôn ngữ liên kết với biểu thức chính quy Biểu thức chính quy được dùng để mô tả ngôn ngữ chính qui. Tổng quát, nếu r là biểu thức chính quy thì ta nói L(r) là ngôn ngữ được sinh ra từ r. Ngôn ngữ liên kết với biểu thức chính quy L( ) = {} L( ) = { } L(a) = {a} L(r1 + r2) = L(r1) L(r2) L(r1 . r2) = L(r1)L(r2) L(r1*) = (L(r1))* L((r1)) = L(r1) Ngôn ngữ L(r) được biểu thị bởi bất kì một biểu thức chính quy r nào, thì được định nghĩa bởi các quy tắc sau. Example 1 L(a* . (a + b)) = L(a*) L(a + b) = (L(a))* (L(a) L(b)) = { , a, aa, aaa, .}{a, b} = {a, aa, aaa, ., b, ab, aab, .} Precedence Rules star-closure > concatenation > union L(a* . a + b) = L(a* . a) L(b) = (L(a* ) L(a)) L(b) = ((L(a))* L(a)) L(b) = ({ , a, aa, aaa, .}{a}) {b} = {a, aa, aaa, ., b} Example 2 r = (a + b)* (a + bb) L(r) = ? Nó biểu thị cho ngôn ngữ L(r) = {a, bb, aa, abb, ba, bbb, }. Hãy xem xét từng phần của biểu thức r. Phần thứ nhất, (a+b)*, đặc trưng cho chuỗi gồm các kí tự a và b. Phần thứ hai, (a + bb) đặc trưng cho a hoặc cho hai kí tự b. Do vậy, L(r) là một tập của tất cả các chuỗi trên {a,b}, được kết thúc bởi một chữ a hay một chuỗi bb. Example 3 r = . | NGÔN NGỮ CHÍNH QUY VÀ VĂN PHẠM CHÍNH QUY Dr. Huỳnh Trung Hiếu Faculty of Information Technology HoChiMinh City University of Industry Regular Languages & Grammars L is regular iff L = L(M) for some DFA M Trong chương này, ta sẽ nghiên cứu những cách khác để biểu diễn ngôn ngữ chính quy. Regular Languages & Grammars Way of representing Way of thinking Regular Expressions L = value of E Regular Expressions Alphabet , và a là các biểu thức chính quy. Những biểu thức này gọi là các biểu thức chính qui nguyên tố. Nếu r1 và r2 là các biểu thức chính quy thì r1 + r2, r1 . r2, r1* và (r1) cũng là các biểu thức chính quy. Một chuỗi gọi là biểu thức chính quy nếu và chỉ nếu nó có thể được xây dựng từ các biểu thức chính quy nguyên tố bởi áp dụng một số hữu hạn lần các quy tắc trong mục 2. Ngôn ngữ liên kết với biểu thức chính quy Biểu thức chính quy được dùng để mô tả ngôn ngữ chính qui. Tổng quát, nếu r là biểu thức chính quy thì ta nói L(r) là ngôn ngữ được sinh ra từ