- BÀI 4: BIỂU THỨC CHÍNH QUY. - Biểu thức chính quy: Sử dụng các toán tử chính quy để biểu diễn một biểu thức mô tả ngôn ngữ. - Ví dụ: (0∪1)0*. - Tất cả các xâu bắt đầu bằng 1 ký tự 0 hoặc 1 và sau đó là một số nào đó các ký tự 0. - Vai trò của Biểu thức chính quy: Là một phương pháp mạnh để mô tả 1 mẫu văn bản nào đó. - Trong một số ngôn ngữ lập trình đều ứng dụng kỹ thuật mô tả mẫu bằng biểu thức chính quy (Regular Expression). - Định nghĩa hình thức của biểu thức chính quy. - Ta nói R là một biểu thức chính quy nếu R là:. - (R 1 ∪ R 2 ) trong đó R 1 và R 2 là các biểu thức chính quy 5. - (R 1 ◦ R 2 ) trong đó R 1 và R 2 là các biểu thức chính quy 6. - trong đó R 1 là một biểu thức chính quy. - Độ ưu tiên của các toán tử chính quy. - Ví dụ về độ ưu tiên toán tử chính quy. - Ví dụ biểu thức chính quy. - 0Σ*0∪1Σ*1∪0∪1 = {w|w bắt đầu và kết thúc bởi cùng 1 ký hiệu}. - Ngôn ngữ của biểu thức chính quy. - Mỗi biểu thức chính quy R đều mô tả một ngôn ngữ → Ngôn ngữ gì?. - Một ngôn ngữ là chính quy nếu và chỉ nếu có một biểu thức chính quy nào đó mô tả nó. - Nếu một ngôn ngữ được mô tả bởi một biểu thức chính quy thì nó là chính quy. - Nếu một ngôn ngữ là chính quy, thì nó được mô tả bởi một biểu thức chính quy. - Từ Hệ quả 1.40 (Sách giáo trình): Nếu 1 NFA đoán nhận A thì A là chính quy → Chuyển đổi R thành một NFA N. - Ví dụ: Chuyển đổi R → NFA. - Chuyển đổi biểu thức chính quy sau thành NFA: (ab∪a)*. - Vì A là ngôn ngữ chính quy → Nó được đoán nhận bởi 1 DFA - Chuyển đổi DFA thành biểu thức chính quy → Cần sử dụng. - Nhãn của các cạnh là các biểu thức chính quy - Chỉ có 1 trạng thái chấp thuận. - Trạng thái chấp thuận không trùng với trạng thái bắt đầu - Không có cạnh nào nối tới trạng thái bắt đầu. - Không có cạnh nào xuất phát từ trạng thái kết thúc. - Loại trừ trạng thái bắt đầu và kết thúc, mọi mũi tên có thể đi từ 1 trạng thái đến các trạng thái còn lại hoặc là tới chính nó. - Chuyển đổi DFA → GNFA. - Thêm trạng thái bắt đầu mới. - Thêm trạng thái kết thúc mới. - Chọn 1 trạng thái và tách nó ra khỏi máy. - Chỉnh sửa phần còn lại sao cho ngôn ngữ tương tự vẫn được đoán nhận → Trạng thái bị tách ra được gọi là q rip. - Lặp lại bước trên cho đến khi máy chỉ còn 2 trạng thái bắt đầu và kết thúc. - Ví dụ. - Chuyển đổi DFA sau thành biểu thức chính quy. - Mỗi biểu thức chính quy R đều mô tả một ngôn ngữ chính quy. - Q: Tập trạng thái (hữu hạn. - R là tập tất cả các biểu thức chính quy trên bộ chữ Σ. - q start : Trạng thái bắt đầu - q accept : Trạng thái kết thúc
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt