edited by
1,543 views
2 votes
2 votes

Consider the following regular expressions:

  1. $r=a(b+a)^*$
  2. $s=a(a+b)^*$
  3. $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) \subseteq L(s) \subseteq L(t)$
  2. $L(r) \supseteq L(s) \supseteq L(t)$
  3. $L(r) \supseteq L(t) \supseteq L(s)$
  4. $L(s) \supseteq L(t) \supseteq L(r)$
edited by

2 Answers

1 votes
1 votes
  1. r=a(b+a)*   L(r)=a,aa,ab,aaabb,….(can give all strings starting with a so superset of both L(s) and L(t)
  2. s=a(a+b)+  L(s)=aa,ab,aaabb,….. (can not give ‘a’) hence  L(s) is subset of L(r)
  3. t=aa*b        L(t) =ab,aab,aaab….  (can not give ‘a’,abb ..) hence  L(t) is subset of L(s) 

so ans is option B)L(r)⊇L(s)⊇L(t)

1 votes
1 votes

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

This regular expression generates all strings which start with “a” and have any number of b’s or a’s following it.

For example, $a, aa, ab, aab, aba, abb, abbbaaa$

(b) s = $a(a+b)^*$

This regular expression also generates all strings which start with “a” and have any number of a’s or b’s following it.

It is worthwhile to note here that both the regular expressions r and s are referring to one and the same language, as $(a+b)^* = (b+a)^*$

(c) t = $aa^*b$t

The regular expression t generates all strings which start with “a”, have any number of a’s following it and always end with a “b”. This class of regular expressions refers to a very small subset of the strings that can be generated by either r or s.

For example, $ab, aab, aaab, aaaab$

Clearly, r and s are equivalent and t is a subset of r (or s).

Hence, we can say, 

$L(r) \supseteq L(s) \supseteq L(t)$

$\therefore$ Option B is correct.

Answer:

Related questions