1 Practice: Another Operation on a Language Define the following operation on languages, OP3, to be: OP3(L)={aabL,b} Give the result of applying OP3 on the following languages (assume strings in the language are created with characters from some alphabet ={a,b,c} : - {a,b,c} - - {abe, def }{abc,cba} - - ab Come up with regular expressions for the following languages (whose strings use alphabet ={a,b,c,$}) 1. {ww contains the special character $ somewhere in the string } 2. {a,b,c} 3. {a,b}{$,c} 4. Any string in the set {aa,bb,cc}, repeated zero times 5. The set of strings that are at least three characters long 6. The set of strings that either contain the $ special char, or are at least three characters long (it may be easiet to assign your previous answers to variables and use those variables here). If you wish, you may additionally use the following regular expression abbreviations: - = any single char in the alphabet of the language - = a sequence of zero or more of any char in the alphabet of the language Remember that a "proof by induction" is just a proof that involves a recursive definition. Further, the structure of the proof should exactly follow the structure of the recursive definition. In this problem, use proof by induction to prove a basic logarithmic identity that you likely learned in algebra class: logxy=ylogx Specifically, prove that this equality is true for all natural number values of y. Make sure your proof: - clearly states that it is a proof by induction, - clearly states the specific "thing" that the induction is "on", - has a base case, which must follow the recursive definition of the "thing", - has a recursive case, that again must follow the recursive definition, - declares an inductive hypothesis, which is an assumption that uses the "smaller" selfreference from the recursive case in the definition, - and uses the inductive hypothesis in the proof of the recursive case. If you need it, your proof may use another logarithmic identity as a known fact: logab=loga+logb In lecture, when proving the statement: A language L is a regular language if and only if there is a regular expression that describes L specifically, in the proof of the reverse direction, we sketched out a conversion function, call it RE2NFA, that given any regular expression as input, converts it to an equivalent NFA. For this problem, you must do two things: 1. Write out the full, recursive definition of the RE2NFA function. Its cases and recursive parts should exactly follow the cases and recursive parts in the formal definition of regular expressions. Further, if you need to write out an NFA, it should be a formal description. (You may assume that the alphabet of L is .) Finally, you may assume and use in your definition additional functions UNION UFA, , CONCAT NFA , and STAR NFA, which correspond to the NFA combination operations we defined together in lecture when proving that these operations are closed. 2. Prove that the conversion performed by RE2NFA "correct". Specifically, answer the following questions: a. When we say that two things (e.g., a regular expression and an NFA) are "equivalent" in this course, what does this mean? b. Now, given a meaning for "equivalent", we can say that the conversion function RE2NFA is "correct" if its input and output are "equivalent". Give a formal (equality) statement for this notion of "correctness". c. Prove the statement that you came up with. The proof should be a proof by induction on regular expressions (make sure to say which one). Thus, the proof needs to follow the recursive definition of regular expressions and should have 6 parts: 3 base cases and 3 recursive cases. Make sure that each recursive case declares and uses an inductive hypothesis assumption