Regular expression in theory of computation solved examples

Solution:

We have the input alphabets ∑ = {a, b, c}.

Here, the resultant regular expression will denote the set of all string over the given input alphabets ∑ = {a, b, c}, which contains no more than three a’s, i.e., it will contains either zero a or one a or two a or three a.

For this, first write the regular expression which denotes zero or one ‘a’. It is-

(λ + a)
Now, we can write either zero ‘a’ or one ‘a’ or two ‘a’ or three ‘a’ as –

(λ + a) (λ + a) (λ + a)

Now, since we have given ∑ = {a, b, c}, as per the problem given the resultant regular expression denotes set of all strings containing no more than three a’s over the given input alphabets ∑ = {a, b, c}.

Thus, we must have to allow the arbitrary regular expression which represent the string not containing a’s over the given input alphabets ∑ = {a, b, c} at the place which marked by ‘X’ (Assumed), as under –

X (λ + a) X (λ + a) X (λ + a) X

Here, the regular expression for the place X can be written as-

(b + c)*

i.e., the regular expression over the given input alphabets ∑ = {a, b, c} which does not contain any ‘a’.

Thus, putting this regular expression at the place marked by X’s in the form of resultant regular expression given above, we will get;

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

This is the required resultant regular expression.