Automata and Formal Language (chapter 3)

Chương 3 của bộ Slide tiếng Anh môn học lý thuyết automata và ngôn ngữ hình thức đầy đủ của trường ĐHBK . Bộ Slide này có tổng cộng 7 chương. | Regular Language and Regular Grammar Objectives Regular Expression and Regular Language Regular Expression vs Regular Language Regular Grammar Regular Expression Alphabet , , a are regular expressions (known as primitive regular expressions). If r1 and r2 are regular expressions, so are r1 + r2, r1 . r2, r1*, and (r1). Operator Precedence parentheses star-closure (*) concatenation (.) union (+) Languages Associated with Regular Expressions Each regular expression stands for a set of strings of symbols in each regular expression represents a language, called regular language r L(r) Example L(a) = {a} L((a + )* ) = { , a, bc, aa, abc, bca, bcbc, aaa, aabc, .} L(a + b +) syntax error Regular Languages 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) Example 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, .} Example r = (a + | Regular Language and Regular Grammar Objectives Regular Expression and Regular Language Regular Expression vs Regular Language Regular Grammar Regular Expression Alphabet , , a are regular expressions (known as primitive regular expressions). If r1 and r2 are regular expressions, so are r1 + r2, r1 . r2, r1*, and (r1). Operator Precedence parentheses star-closure (*) concatenation (.) union (+) Languages Associated with Regular Expressions Each regular expression stands for a set of strings of symbols in each regular expression represents a language, called regular language r L(r) Example L(a) = {a} L((a + )* ) = { , a, bc, aa, abc, bca, bcbc, aaa, aabc, .} L(a + b +) syntax error Regular Languages 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) Example 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, .} Example r = (a + b)* (a + bb) L(r) = ? Example r = (a + b)* (a + bb) L(r) = {w| w ends with a or bb} Example r = (aa)* (bb)* b L(r) = ? Example r = (aa)* (bb)* b L(r) = {a2nb2m+1: n 0, m 0} Example L(r) = {w {0, 1}* | w has at least one pair of consecutive zeros} r =? Example L(r) = {w {0, 1}* | w has at least one pair of consecutive zeros} r = (0 + 1)* 00 (0 + 1)* Example L(r) = {w {0, 1}* | w has no pair of consecutive zeros} r = ? Example L(r) = {w {0, 1}* | w has no pair of consecutive zeros} r = (1 + 01)* (0 + ) Equivalent Regular Expression r1 and r2 are equivalent iff L(r1) = L(r2) Example r1 = a . (b + c) r2 = a . b + a . c L(r1) = L(r2) = {ab, ac} Regular Expressions and Languages Given a regular expression r, there exists an NFA that accepts L(r) L(r) is a regular language Primitive NFAs q0 q1 NFA that accepts q0 q1 NFA that accepts { } q0 q1 NFA that accepts {a} a Primitive NFAs (cont’d) NFA that accepts L(r1 + r2) M(r1) M(r2) Primitive .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.