Question? Leave a message!




Regular Languages

Regular Languages
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Website URL
Comment
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, k-1) + R(i, k, k-1) R(k, k, k-1) R(k, j, k-1) R(i, j, k-1) q 1 a q j q q i j q q 2 i q k-1 a R(k, j, k-1) q R(i, k, k-1) i q k R(k, k, k-1) 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, k-1) + R(i, k, k-1) R(k, k, k-1) R(k, j, k-1) www.ThesisScientist.com