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

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.