Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



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:





Solution

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

This represents all strings over $\{a,b\}$ that start with $a$.

So,

$L(r)=\{a,aa,ab,aaa,aab,aba,\ldots\}$

For $s=a(a+b)^+$:

Here, after first $a$, at least one more symbol from $\{a,b\}$ must be present.

So, $s$ represents all strings over $\{a,b\}$ that start with $a$ and have length at least $2$.

Therefore,

$L(s)\subseteq L(r)$

For $t=aa^*b$:

This represents strings of the form:

$ab,aab,aaab,aaaab,\ldots$

So, every string of $L(t)$ starts with $a$ and has length at least $2$.

Therefore,

$L(t)\subseteq L(s)$

Hence,

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


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...