3.1 REGULAR EXPRESSIONS 75 Even though this looks similar to Example 3.5, the an

Question

3.1 REGULAR EXPRESSIONS 75 Even though this looks similar to Example 3.5, the answer is harder to One helpful observation is that whenever a 0 occurs, it must be followed immediately by a 1. Such a substring may be preceded and followed by an arbitrary number of 1's. This suggests that the answer involves the repetition of strings of the form 1... that is, the language denoted by the regular However, the answer is sti incomplete, since the strings ending in o or consisting of all I's are unaccounted for. After taking care of these special cases we arrive at the answer r 011') (o A) 1 (0+ A). If we reason slightly differently, we might come up with another answer. If we see Las the repetition of the strings 1 and 01, the shorter expression (1 01) (0 A) might be reached. Although the two expressions look different, both answers are correct, as they denote the same language. Generally, there are an unlimited mamber of regular expressions for any given language. Note that this language is the complement of the language in Example 3.5. However, the regular expressions are not very similar and do not suggest clearly the close relationship between the languages. The last example introduces the notion of equivalence of regular ex- pressions. We say the two regular expressions are equivalent if they denote the same language. One can derive a variety of rules for simplifying regular expressions (see Exercise 20 in the following exercise section), but since we have little need for such manipulations we will not pursue this. EXERCISES Find all strings in L (a 6) (a ab) of length less than four. ample 3.5? 3. Show that r +01) (0+ 1 also denotes the language in Example 36. Find two other equivalent expressions. Find a regular expression for the set fa n 3 m is even). a. Find a regular expression for the set (a"b" (n m) is even) 6. Give regular expressions for the following languages. 4, m s 3)

Explanation / Answer

1. All strings of length less than four in L = ( (a+b)* b ( a+ab )*) : [ b, ab , ba , aab , bab , bbb , aba , bba , abb ,aab , baa ]

5. regular expression for set { an bm , (n+m) is even } will be as

(i) n and m both are even = (aa)* (bb)* ;

(ii) n and m both are odd but by adding them up they become even = a(aa)* b(bb)*

thus the regular expression wll be as (aa)*(bb)* + a(aa)* b(bb)*

4. regular expression for set {an bm , n>=3 m is even } will be as

for n>=3 it will be aaaa* and for m is even it will be (bb)*

thus comletely it will be aaaa*(bb)*

6. (b) regular expression for language { anbm : n<4 ,m <=3 } will be

{an : n<4 } =    + a + aa + aaa

{bm : m<=3 } = + b + bb + bbb

together it will be as ( + a + aa + aaa) ( + b + bb + bbb )

6.(a) regular expression for language { an bm : n >= 4 , m <=3 }

for {an : n>= 4 } it will be aaaa*

for { bm : m<=3 } it will be  ( + b + bb + bbb )

togrther it will be aaaa* ( + b + bb + bbb ).

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.