This chapter includes contents: Example of prefixes of a language, Theorem: pref(Q in R) is regular, proof, example, Decidablity, deciding whether two languages are regular or not?, method 1, example, method 2, example. | Lecture # 5 Theory Of Automata By Dr. MM Alam 1 Lecture#4 Recap Recursive way of defining languages Recursive way examples Regular expressions Regular expression examples Construct a regular expression for all words that contain exactly two b’s or exactly three b’s, not more. a*ba*ba* + a*ba*ba*ba* or a*(b + Λ)a*ba*ba* Construct a regular expression for: (i) all strings that end in a double letter. (ii) all strings that do not end in a double letter (i) (a + b)*(aa + bb) (ii) (a + b)*(ab + ba) + a + b + Λ Construct a regular expression for all strings that have exactly one double letter in them (b + Λ)(ab)*aa(ba)*(b + Λ) + (a + Λ)(ba)*bb(ab)*(a + Λ) Construct a regular expression for all strings in which the letter b is never tripled. This means that no word contains the substring bbb (Λ + b + bb)(a + ab + abb)* Words can be empty and start and end with a or b. A compulsory ‘a’ is inserted between all repetitions of b’s. Construct a regular expression for all words in which a is . | Lecture # 5 Theory Of Automata By Dr. MM Alam 1 Lecture#4 Recap Recursive way of defining languages Recursive way examples Regular expressions Regular expression examples Construct a regular expression for all words that contain exactly two b’s or exactly three b’s, not more. a*ba*ba* + a*ba*ba*ba* or a*(b + Λ)a*ba*ba* Construct a regular expression for: (i) all strings that end in a double letter. (ii) all strings that do not end in a double letter (i) (a + b)*(aa + bb) (ii) (a + b)*(ab + ba) + a + b + Λ Construct a regular expression for all strings that have exactly one double letter in them (b + Λ)(ab)*aa(ba)*(b + Λ) + (a + Λ)(ba)*bb(ab)*(a + Λ) Construct a regular expression for all strings in which the letter b is never tripled. This means that no word contains the substring bbb (Λ + b + bb)(a + ab + abb)* Words can be empty and start and end with a or b. A compulsory ‘a’ is inserted between all repetitions of b’s. Construct a regular expression for all words in which a is tripled or b is tripled, but not both. This means each word contains the substring aaa or the substring bbb but not both. (Λ + b + bb)(a + ab + abb)*aaa(Λ + b + bb)(a + ab + abb)* + (Λ + a + aa)(b + ba + baa)*bbb(Λ + a + aa)(b + ba + baa)* Let r1, r2, and r3 be three regular expressions. Show that the language associated with (r1 + r2)r3 is the same as the language associated with r1r3 + r2r3. Show that r1(r2 + r3) is equivalent to r1r2 + r1r3. This will be the same as providing a ‘distributive law’ for regular expressions. (r1+ r2)r3: The first expression can be either r1 or r2. The second expression is always r3. There are two possibilities for this language: r1r3 or r2r3. r1(r2 + r3): The first expression is always r1. It is followed by either r2 or r3. There are two possibilities for this language: r1r2 or r1r3. Question Can a language be expressed by more than one regular expressions, while given that a unique language is generated by that regular expression? Also known as Finite state
