Peter Linz Edition 4 Exercise 3.1 Question 16.c (Page No. 76)

Question

Give regular expression for the following language on $\sum = \left \{ a,b,c \right \}$

All strings that contain at least one occurrence of each symbol in $\sum$

Answer 1

The problem here is that we cannot assume the symbols are in any particular order. We have no way of saying "in any order", so we have to list the possible orders:

abc + acb + bac + bca + cab + cba

To make it easier to see what's happening, let's put an X in every place we want to allow an arbitrary string:

XaXbXcX + XaXcXbX + XbXaXcX + XbXcXaX + XcXaXbX + XcXbXaX

Where X is any arbitrary string i.e. (a+b+c)*

Finally, replacing the X's with (a+b+c)* gives the final (unwieldy) answer :

(a+b+c)*a(a+b+c)*b(a+b+c)*c(a+b+c)* + (a+b+c)*a(a+b+c)*c(a+b+c)*b(a+b+c)* + (a+b+c)*b(a+b+c)*a(a+b+c)*c(a+b+c)* + (a+b+c)*b(a+b+c)*c(a+b+c)*a(a+b+c)* + (a+b+c)*c(a+b+c)*a(a+b+c)*b(a+b+c)* + (a+b+c)*c(a+b+c)*b(a+b+c)*a(a+b+c)*

Comments

Sir, what about (a⁺ b⁺ c⁺)⁺

---

@Harsh Kumar 

$(a^+b^+c^+)^+$ doesn’t generate many strings which are in the given language. For instance, $bac, ccba$ etc.

Answer 2

(a+b+c)*a(a+b+c)*b(a+b+c)*c(a+b+c)* + (a+b+c)*a(a+b+c)*c(a+b+c)*b(a+b+c)* + (a+b+c)*b(a+b+c)*a(a+b+c)*c(a+b+c)*  +

(a+b+c)*b(a+b+c)*c(a+b+c)*a(a+b+c)* +  (a+b+c)*c(a+b+c)*b(a+b+c)*a(a+b+c)*  + (a+b+c)*c(a+b+c)*a(a+b+c)*b(a+b+c)*