Course: Theory Computation

Topic: Regular Expression

Ex. 1: Find the shortest string that is not in the language represented by the regular expression a*(ab)*b*. Ex. 2: For the two regular expressions r = a* + b* and r2 = ab* + ba* + b*a + (a*b)* (a) find a string corresponding to r2 but not to ri and (b) find a string corresponding to both r and r2. Ex. 3: Let r and r2 be arbitrary regular expressions over some alphabet. Find a simple (the shortest and with the smallest nesting of * and +) regular expression which is equal to the following regular expressions. (r + r2 + rr2 + r2r)* Ex. 4: Find a regular expression corresponding to the language L over the alphabet {a,b } defined recursively as follows: Basis Clause: EL Inductive Clause: If x EL, then aabx E L and xbb EL. Extremal Clause: Nothing is in L unless it can be obtained from the above two clauses. Ex. 5: Find a regular expression corresponding to the language of all strings over the alphabet {db} that contain exactly two a's. Ex. 6: Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that do not end with ab