tailieunhanh - Automata and Formal Language (chapter 4)

Chương 4 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. | Chapter 4: Properties of Regular Languages Quan Thanh Tho qttho@ Theorem If L1 and L2 are regular, then so are L1 L2, L1 L2 , L1L2 , L1, L1*. (The family of regular languages is closed under intersection, union, concatenation, complement, and star-closure.) Proof L1 = L(r1) L2 = L(r2) L(r1 + r2) = L(r1) L(r2) L(r1 . r2) = L(r1)L(r2) L(r1*) = (L(r1))* Proof (cont’d) M = (Q, , , q0, F) accepts L1. M = (Q, , , q0, Q – F) accepts L1. Proof (cont’d) M1 = (Q, , 1, q0, F1) accepts L1. M2 = (P, , 2, p0, F2) accepts L2. q0 qf a1 an p0 pf a1 an 2(pj, a) = pl 1(qi, a) = qk 1((qi, pj), a) = (qk, pl) Example L1 = {abn | n 0} L2 = {anb | n 0} L1 L2 = {ab} Example Find intersection dfa of L1={a2nbm: n, m 0} and L2={a3nb2m: n, m 0} p1 p0 p2 p3 a a a b b b L2 p4 q1 p1 q0 p0 q2 p4 q1 p2 q2 p3 q0 p2 q0 p1 q1 p0 a a a a a a b b b L1 L2 q1 q0 q2 a a b L1 b Theorem 2 The family of regular languages is closed under reversal: If L is regular, then so is LR. . | Chapter 4: Properties of Regular Languages Quan Thanh Tho qttho@ Theorem If L1 and L2 are regular, then so are L1 L2, L1 L2 , L1L2 , L1, L1*. (The family of regular languages is closed under intersection, union, concatenation, complement, and star-closure.) Proof L1 = L(r1) L2 = L(r2) L(r1 + r2) = L(r1) L(r2) L(r1 . r2) = L(r1)L(r2) L(r1*) = (L(r1))* Proof (cont’d) M = (Q, , , q0, F) accepts L1. M = (Q, , , q0, Q – F) accepts L1. Proof (cont’d) M1 = (Q, , 1, q0, F1) accepts L1. M2 = (P, , 2, p0, F2) accepts L2. q0 qf a1 an p0 pf a1 an 2(pj, a) = pl 1(qi, a) = qk 1((qi, pj), a) = (qk, pl) Example L1 = {abn | n 0} L2 = {anb | n 0} L1 L2 = {ab} Example Find intersection dfa of L1={a2nbm: n, m 0} and L2={a3nb2m: n, m 0} p1 p0 p2 p3 a a a b b b L2 p4 q1 p1 q0 p0 q2 p4 q1 p2 q2 p3 q0 p2 q0 p1 q1 p0 a a a a a a b b b L1 L2 q1 q0 q2 a a b L1 b Theorem 2 The family of regular languages is closed under reversal: If L is regular, then so is LR. Proof ? Suppose and are alphabets. h: * is called a homomorphism Homomorphism Homomorphism (cont’d) Extended definition: w = a1a2 . an h(w) = h(a1)h(a2) . h(an) Homomorphism (cont’d) If L is a language on , then its homomorphic image is defined as: h(L) = {h(w): w L} Example = {a, b} = {a, b, c} h(a) = ab h(b) = bbc h(aba) = abbbcab L = {aa, aba} h(L) = {abab, abbbcab} Homomorphism (cont’d) If r is a regular expression on , then the regular expression h(r) is obtained by applying the homomorphism to each symbol of r. Example = {a, b} = {b, c, d} h(a) = dbcc h(b) = bdc r = (a + b*)(aa)* h(r) = (dbcc + (bdc)*)(dbccdbcc)* Theorem The family of regular languages is closed under homomorphism: If L is regular, then so is h(L). Proof Let L(r) = L for some regular expression r. Prove: h(L(r)) = L(h(r)). Right Quotient Let L1 and L2 be languages on the same alphabet. Then the right quotient of L1 with L2 is defined as: L1/L2 = {x | xy L1 and y L2} .