Give regular expressions for the following languages on Σ = {a, b, c}- solution of Peter Linz

 

Give regular expressions for the following languages on Σ = {a, b, c}.

 (a) all strings containing exactly one a, 

 (b) all strings containing no more than three a’s,

 (c) all strings that contain at least one occurrence of each symbol in Σ,

 (d) all strings that contain no run of a's of length greater than two,

 (e) all strings in which all runs of a's have lengths that are multiples of three.

( an-introduction-to-formal-languages-and-automata- Peter Linz, question no. 16, section 3.1 )

Solution:

 (a) all strings containing exactly one a, 

=> (b+c)* a  (b+c)*

 (b) all strings containing no more than three a’s,

=>(b+c)*(a+λ)(b+c)*(a+λ)(b+c)*(a+λ)(b+c)*

(c) all strings that contain at least one occurrence of each symbol in Σ,

=> (a+b+c)*a(a+b+c)*b(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)*a(a+b+c)*c(a+b+c)*b(a+b+c)* +(a+b+c)* c (a+b+c)* b (a+b+c)* a (a+b+c)* +  (a+b+c)* b (a+b+c)* a (a+b+c)* c(a+b+c)*

(d) all strings that contain no run of a's of length greater than two,

=> (b+c)* (λ+a+aa)(b+c)*( (b+c) (b+c)* (λ +a +aa) (b+c)*)*

 (e) all strings in which all runs of a's have lengths that are multiples of three.

=> ( aaa +b +c)*