Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 TP.HCM. 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 3.1 L(a) = {a} L((a + b.c)* ) = { , 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 3.2 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 3.3 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 3.1 L(a) = {a} L((a + b.c)* ) = { , 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 3.2 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 3.3 r = (a + b)* (a + bb) L(r) = ? Example 3.3 r = (a + b)* (a + bb) L(r) = {w| w ends with a or bb} Example 3.5 r = (aa)* (bb)* b L(r) = ? Example 3.5 r = (aa)* (bb)* b L(r) = {a2nb2m+1: n 0, m 0} Example 3.6 L(r) = {w {0, 1}* | w has at least one pair of consecutive zeros} r =? Example 3.6 L(r) = {w {0, 1}* | w has at least one pair of consecutive zeros} r = (0 + 1)* 00 (0 + 1)* Example 3.7 L(r) = {w {0, 1}* | w has no pair of consecutive zeros} r = ? Example 3.7 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 3.8 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 .
