Question? Leave a message!




Regular Languages

Regular Languages
Regular LanguagesOutline • Regular expressions • Regular languages • Equivalence between languages accepted by FA and regular languages • Closure Properties www.ThesisScientist.comRegular Expressions Regular expression over alphabet  • is a regular expression. • is a regular expression. • For any a, a is a regular expression. • If r and r are regular expressions, then 1 2 – (r + r ) is a regular expression. 1 2 – (r r ) is a regular expression. 1 2 – (r ) is a regular expression. 1 • Nothing else is a regular expression. www.ThesisScientist.comRegularLanguages • is a regular language corresponding to the regular expression . •  is a regular language corresponding to the regular expression . • For any symbol a, a is a regular language corresponding to the regular expression a. • If L and L are regular languages corresponding to 1 2 the regular expression r and r , then 1 2 – LL , LL , and L are regular languages 1 2 1 2 1 corresponding to (r + r ) , (r r ), and (r ). 1 2 1 2 1 www.ThesisScientist.comSimple examples Let = 0,1. •   does not contain 1’s – (0 ) •   contains 1’s only + – (1(1 )) (which can can be denoted by (1 )) • – ((0+1) ) •   contains only 0’s or only 1’s – ((00 )+(11 )) 0 + 1  (0+1) www.ThesisScientist.comSome more notations Let = 0,1. • Parentheses in regular expressions can be omitted when the order of evaluation is clear. – ((0+1) )  0+1 – ((0 )+(1 )) = 0 + 1 • For concatenation,  can be omitted. n • r r r… r is denoted by r . n times www.ThesisScientist.comMore complex examples Let  = 0,1. •   contains odd number of 1’s – 0(1010)10 •  any two 0’s in  are separated by three 1’s – 1(0111)01 + 1 •   is a binary number divisible by 4 – (0+1)00 •   does not contain 11 + – 0(10 ) (1+) or (0+10) (1+) www.ThesisScientist.comNotation Let r be a regular expression. The regular language corresponding to the regular expression r is denoted by L(r). www.ThesisScientist.comSome rules for language operations Let r, s and t be languages over 0,1 r + =  + r = r r + s = s + r r  = r = r r = r =  r(s + t) = rs + rt + r = r r www.ThesisScientist.comRewrite rules for regular expressions Let r, s and t be regular expressions over 0,1.  =   =  + (r + ) = r r = r(r + ) = r r = (r) (rs) = (r + s) www.ThesisScientist.comClosure properties of the class of regular languages (Part 1) Theorem: The class of regular languages is closed under union, concatenation, and Kleene’s star. Proof: Let L and L be regular languages over. 1 2 Then, there are regular expressions r and r 1 2 corresponding to L and L . 1 2 By the definition of regular expression and regular languages, r +r ,rr , and r are regular 1 2 1 2 1 expressions corresponding to LL , LL , and L . 1 2 1 2 1 Thus, the class of regular languages is closed under union, concatenation, and Kleene’s star. www.ThesisScientist.comEquivalence of language accepted by FA and regular languages To show that the languages accepted by FA and regular languages are equivalent, we need to prove: • For any regular language L, there exists an FA M such that L = L(M). • For any FA M, L(M) is a regular language. www.ThesisScientist.comFor any regular language L, there exists an FA M such that L = L(M) Proof: Let L be a regular language. Then,  a regular expression r corresponding to L. We construct an NFA M, from the regular expression r, such that L=L(M). Basis:  If r = , M is s f If r = , M is s a If r = a for some a , M is s f www.ThesisScientist.comProof (cont’d) Induction hypotheses: Let r and r be regular expressions 1 2 with less than n operations. And, there are NFA’s M 1 and M accepting regular languages corresponding 2 to L(r ) and L(r ). 1 2 Induction step: Let r be a regular expression with n operations. We construct an NFA accepting L(r). r can be in the form of either r +r , rr , or r , for 1 2 1 2 1 regular expressions r and r with less than n 1 2 operations. www.ThesisScientist.comProof (cont’d) s f  1 1 If r = r +r , then M is s 1 2 s f 2 2   s f s f If r = rr , then M is 1 1 2 2 1 2    s s f f If r = r , then M is 1 1 1  Therefore, there is an NFA accepting L(r) for any regular expression r. www.ThesisScientist.comConstructing NFA for regular expressions s + • 0 (10 )  (1+) 0 0   + 1 0 10  +  (10 ) 0  1   1 1+    www.ThesisScientist.comSome Observations s • Can these  two states 0 be merged   NO 1 0 • Be careful   when you 0  decide to 1   merge some  states.  www.ThesisScientist.comFor any FA M, L(M) is a regular language Proof: Let M = (Q, , , q , F) be an FA, where Q=q 1 1 i  i  n for some positive integer n. Let R(i, j, k) be the set of all strings in that drive M from state q to state q while passing through any i j state q , for l  k. (i and j can be any states) l q l q i q j q l' www.ThesisScientist.comProof (cont’d) R(i, j, 0) = + a if i j qj (qi, a) R(i, j, 0) = + a +  if i= j qj (qi, a) R(i, j, k) = R(i, j, k1) + R(i, k, k1) R(k, k, k1) R(k, j, k1) R(i, j, k1) q 1 a q j q q i j q q 2 i q k1 a R(k, j, k1) q R(i, k, k1) i q k R(k, k, k1) www.ThesisScientist.comProof (cont’d) Then, L(M) = + R(1, f, n) for all q in F. f R(i, j, 0) = + a if i j qj (qi, a) R(i, j, 1) = a (q , a) = q +  if i= j i j R(i, j, k) = R(i, j, k1) + R(i, k, k1) R(k, k, k1) R(k, j, k1) www.ThesisScientist.comProof (cont’d) We prove that L(M) is a regular language by showing that there is a regular expression corresponding to L(M), by induction. Basis: R(i, j, 0) corresponds to a regular expression a if i j and a + if i= j for some a. Induction hypotheses: Let R(i, j,k1) correspond to a regular expression, for any i, j, k n. www.ThesisScientist.comProof (cont’d) Induction step: R(i, j, k) = R(i, j, k1)  R(i, k, k1) R(k, k, k1) R(k, j, k1) also corresponds to a regular expression because R(i, j, k1), R(i, k, k1), R(k, k, k 1)and R(k, j, k1) correspond to some regular expressions and union, concatenation, and Kleene’s star are allowed in regular expressions. Therefore, L(M) is also a regular language because L(M) = + R(1, f, n) for all q in F. f www.ThesisScientist.comFind a regular expression for a DFA a  q q 2 5 aba + abab (babab+a) baba b ba b ba ba b a a aba (+b(babab+a) baba) b q q 1 3 a ba a b ba ba b  a ba b q 4 www.ThesisScientist.comPumping Lemma Let L be a regular language. Any language L is not a regular language if for any Then, there exists an integer integer n0 , there is a n0 such that for every string string x in L such that x in L that xn, there are xn, for any strings u, v, strings u, v, and w such that and w, – x = u v w, – v , – x  u v w, or – v = , or – u v  n, and k – for all k  0, u v w is also in L. – Not (u v  n), or k – there is k  0, u v w is not in L www.ThesisScientist.comPumping Lemma Any language L is not a regular language if • for any integer n0 , • there is a string x in L such that xn, • for any strings u, v and w, such that x = u v w, v , and u v  n, k –there is k  0, u v w is not in L www.ThesisScientist.comUsing Pumping Lemma If you pick a wrong x, your proof will fail It does not • Given a language L. mean that L is regular • Let n be any integer 0 . • Choose a string x in L that xn. • Consider all possible ways to chop x into u, v and w such that v , and uv  n. • For all possible u, v, and w, show that there k is k  0 such that u v w is not in L. • Then, we can conclude that L is not regular. www.ThesisScientist.comi i Prove 0 1 i 0 is not regular i i Let L = 0 1 i 0. Let n be any integer 0. n n Let x = 0 1 . Make sure that x is in L and xn. The only possible way to chop x into u, v, and w such that v, and u v  n is: p q npq n u = 0 , v = 0 , w = 0 1 , where 0pn and 0qn k Show that there is k 0, u v w is not in L. qk k p npq n p+qk+(npq) n n+q(k1 n ) u v w = 0 0 0 1 = 0 1 = 0 1 k If k 1, then n+q(k1)  n and u v w is not in L. Then, L is not regular. www.ThesisScientist.comi i Prove 0 1 i  0 is not regular i i Let L = 0 1 i 0. Let n be any integer 0, and m= n/2. m m Let x = 0 1 . Make sure that x is in L and xn. Possible ways to chop x into u, v, and w such that v, and u v  n are: p q mpq m – u = 0 , v = 0 , w = 0 1 , where 0pm and 0qm p mp q mq – u = 0 , v = 0 1 , w = 1 , where 0pm and 0qm m p q mpq – u = 0 1 , v = 1 , w = 1 , where 0pm and 0qm www.ThesisScientist.comi i Prove 0 1 i 0 is not regular k Show that there is k 0, u v w is not in L. p q mpq m – u=0 , v=0 , w= 0 1 , where where 0pm and 0qm k p qk mpq m m+q(k1) m u v w = 0 0 0 1 = 0 1 is not in L if k1. p mp q mq – u=0 , v=0 1 , w=1 , where where 0pm and 0qm k p mp q k mq u v w = 0 (0 1 ) 1 is not in L if k 1. m p q mpq – u=0 1 , v=1 , w=1 , where where 0pm and 0qm k m p qk mpq m m+q(k1) u v w = 0 1 1 1 = 0 1 is not in L if k1. Then, L is not regular. www.ThesisScientist.comi Prove 1 i is prime is not regular i Let L = 1 i is prime. Let n be any integer 0. p Let p be a prime  n, and w = 1 . Only one possible way to chop w into x, y, and z such that y, and x y  n is: q r pqr x = 1 , y = 1 , z = 1 , where 0qn and 0rn k Show that there is k 0, x y z is not in L. k q rk pqr q+rk+(pqr) p+r(k1) x y z = 1 1 1 = 1 = 1 If k=p+1, then p+r(k1) = p(r+1), which is not a prime. k Then, x y z is not in L. Then, L is not regular. www.ThesisScientist.comUsing closure property Let  be a binary operation on languages and the class of regular languages is closed under . ( can be , , or ) • If L and L are regular, then LL is regular. 1 2 1 2 • If LL is not regular, then L or L are not 1 2 1 2 regular. • If LL is not regular but L is regular, then 1 2 2 L is not regular. 1 www.ThesisScientist.com Prove that w0,1 the number of 0’s and 1’s in w are equal is not regular Let L=w0,1 the number of 0’s and 1’s in w are equal. i i Let R= 01 i  0. R = 0 1 L We already prove that R is not regular. But 01 is regular. Then, L is not regular. www.ThesisScientist.comUsing closure property Let  be a unary operation on a language and the class of regular languages is closed under . ( can be complement or ) • If L is regular, then L is regular. • If L is not regular, then L is not regular. www.ThesisScientist.com Prove that w0,1 the number of 0’s and 1’s in w are not equal is not regular Let L = w0,1 the number of 0’s and 1’s in w are not equal. Let R =L = w0,1 the number of 0’s and 1’s in w are equal. We already prove that R is not regular. Then, L is not regular. www.ThesisScientist.comCheck list  Find the language described by a  Construct an FA or a regular exp. regular exp. for the intersection, union,  Construct regular exp. describing a concatenation, given language complementation, and  Convert a regular exp. into an FA Kleene’s star of regular  Convert an FA into a regular exp. languages  Prove a language is regular  Prove other closure – By constructing a regular exp. properties of the class of – By constructing an FA regular languages – By using closure properties  Surprise www.ThesisScientist.com
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SamuelHunt
User Type:
Teacher
Country:
United Arab Emirates
Uploaded Date:
21-07-2017