Question

Consider the following regular expressions:

(a) r = a(b + a)*

(b) s = a(a + b)⁺

(c) t = aa*b

Choose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:

1. L(r) ⊆ L(s) ⊆ L(t) 
2. L(r) ⊇ L(s) ⊇ L(t) 
3. L(r) ⊇ L(t) ⊇ L(s)
4. L(s) ⊇ L(t) ⊇ L(r)

Answer 1

Correct Answer - Option 2 : L(r) ⊇ L(s) ⊇ L(t) 

The correct answer is option 2

Explanation:

L(r) = {a, aa, ab, aaa, aab, .... } This is a set of all strings starting with 'a'

L(s) = {aa, ab, aaa, aab, .... } This is a set of all strings starting with 'aa' or 'ab'

L(t) = {ab, aab, aaab, aaaab, ...} This a set of all strings starting with 'a', ending with 'b' and contains any number of 'a's in between them.

Therefore L(r) ⊇ L(s) ⊇ L(t)

* represents 0 or more number of symbols.

+ represents 1 or more number of symbols.