Regular expressions vs. Unix regular expressions. Regular expressions and Unix regular expressions have some superficial differences,...

 

Transcribed Image Text:

Regular expressions vs. Unix regular expressions. Regular expressions and Unix regular expressions have some superficial differences, but also some deeper ones that affect the class of languages recognized. (a) Unix regular expressions have quantifiers: if a is a regular expression, a{m,n} is a regular expression that matches at least m and no more than n strings that match a. More formally, it matches all strings w(1)...w(¹) where m < 1 ≤ n, and for all i such that 1≤ i ≤l, w(¹) matches a. Prove that for any regular expression with quantifiers, there is an equivalent regular expression without quantifiers. (b) Unix regular expressions have backreferences.¹ Give an example of a Unix regular expression that uses backreferences to describe a nonregular lan- guage, and prove that this language is not regular. We want you to get practice writing a non-regularity proof, so although you may use Ex- amples 1.73-77, do not simply cite one of them; please write out a full proof. Regular expressions vs. Unix regular expressions. Regular expressions and Unix regular expressions have some superficial differences, but also some deeper ones that affect the class of languages recognized. (a) Unix regular expressions have quantifiers: if a is a regular expression, a{m,n} is a regular expression that matches at least m and no more than n strings that match a. More formally, it matches all strings w(1)...w(¹) where m < 1 ≤ n, and for all i such that 1≤ i ≤l, w(¹) matches a. Prove that for any regular expression with quantifiers, there is an equivalent regular expression without quantifiers. (b) Unix regular expressions have backreferences.¹ Give an example of a Unix regular expression that uses backreferences to describe a nonregular lan- guage, and prove that this language is not regular. We want you to get practice writing a non-regularity proof, so although you may use Ex- amples 1.73-77, do not simply cite one of them; please write out a full proof.