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

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:23

Thêm vào BST

Báo xấu

355
lượt xem 33
download

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

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....

Chủ đề:

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

Lưu

Nội dung Text: Chương 3 - Ngôn ngữ chính quy và văn phạm chính quy

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. 2
Regular Languages & Grammars Way of representing Way of thinking 3
Regular Expressions L = value of E 4
Regular Expressions Alphabet Σ 1. ∅, λ 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, 1. 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ó 2. 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. 5
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 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. L(∅) = {} 1. L(λ ) = {λ } 2. L(a) = {a} 3. L(r1 + r2) = L(r1)∪L(r2) 4. L(r1 . r2) = L(r1)L(r2) 5. L(r1*) = (L(r1))* 6. L((r1)) = L(r1) 7. 7
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, ...} 8
Precedence Rules starclosure > 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} 9
Example 2 r = (a + b)* (a + bb) L(r) = ? 10
Example 3 r = (aa)* (bb)* b L(r) = ? 11
Example 4 L(r) = {w∈{0, 1}* | w có ít nhất 1 cặp số 0 liên tiếp} r = ? 12
Example 4 L(r) = {w∈{0, 1}* | w has at least one pair of consecutive zeros} r = (0 + 1)* 00 (0 + 1)* 13
Example 5 L(r) = {w∈{0, 1}* | w has no pair of consecutive zeros} r = ? 14
Example 5 L(r) = {w∈{0, 1}* | w has no pair of consecutive zeros} r = (1 + 01)* (0 + λ ) 15
Equivalent Regular Expressions r1 and r2 are equivalent iff L(r1) = L(r2) 16
Example 6 r1 = a . (b + c) r2 = a . b + a . c L(r1) = L(r2) = {ab, ac} 17
Homework Exercises: 1, 4, 5, 6, 7, 13, 23 of Section 3.1  Linz’s book. 18
Regular Expressions & Languages Given a regular expression r, there exists an NFA that accepts L(r). 19
Regular Expressions & Languages NFA that accepts ∅ q0 q1 λ NFA that accepts {λ } q0 q1 a NFA that accepts {a} q0 q1 20