Bài giảng Tin học lý thuyết - Chương 4: Văn phạm chính quy và các tính chất

Chương 4: Văn phạm chính quy & các tính chất Nội dung: • Văn phạm chính quy (RG: Regular Grammar) • Sự tương đương giữa RG và FA • Bổ đề bơm cho tập hợp chính quy • Tính chất đóng của tập hợp chính quy 1 Văn phạm chính quy Văn phạm chính quy: là văn phạm mà tất cả các luật sinh của nó đều có dạng tuyến tính trái (hoặc tuyến tính phải) • Tuyến tính trái: dạng A • Tuyến tính phải: dạng A Bw hoặc A w wB hoặc A w Văn phạm chính quy, ngôn ngữ chính quy, biểu thức chính quy và tập hợp chính quy: • Văn phạm chính quy sinh ra ngôn ngữ chính quy • Ngôn ngữ chính quy có thể được ký hiệu đơn giản bằng một biểu thức chính quy • Tập hợp các chuỗi được ký hiệu bởi một biểu thức chính quy được gọi là tập hợp chính quy Sự tương đương giữa RG & FA Định lý 4.1: Nếu L được sinh ra từ một văn phạm chính quy thì L là tập hợp chính quy Ý nghĩa: một văn phạm chính quy có thể được biểu diễn bởi một Automata hữu hạn. Ví dụ: xét văn phạm tuyến tính phải: S 0A ; A 10A | • Nếu A là một biến: δ([A], ε) = { | A là một luật sinh} • Nếu a là một ký hiệu kết thúc: δ([a ], a) = { [ ] } • Trạng thái bắt đầu [S], trạng thái kết thúc [ε] Start [S] [0A] 0 [A] [ ] 1 [10A] 3 Sự tương đương giữa RG & FA Ví dụ: xét văn phạm tuyến tính trái: S S10 | 0 • Đảo ngược văn phạm tuyến tính trái tuyến tính phải S 01S | 0 1 Start [S] [01S] 0 [1S] [0] 0 [ ] • Đảo ngược automata Start [ ] 0 [0] [S] 1 [1S] 0 [01S] Sự tương đương giữa RG & FA Định lý 4.2: Nếu L là một tập hợp chính quy thì L được sinh ra từ một văn phạm tuyến tính trái hoặc một văn phạm tuyến tính phải nào đó Ý nghĩa: một Automata hữu hạn có thể được biểu diễn bởi một văn phạm chính quy. Ví dụ: xét DFA cho 0(10)* 1 Start A 0 B 0 C 1 0 1 D 0, 1 5 ... - tailieumienphi.vn