TAILIEUCHUNG - 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
đang nạp các trang xem trước