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 languages:

$L_1=\{a^{2^z}\mid z\text{ is an integer}\}$

$L_2=\{a^{2z}\mid z\ge 0\}$

$L_3=\{\omega\omega\mid \omega\in\{a,b\}^*\}$

Which of the languages is or are regular?

Choose the correct answer from the options given below:





Solution

For $L_1$:

$L_1=\{a^{2^z}\mid z\text{ is an integer}\}$

The possible lengths are:

$1,2,4,8,16,32,\ldots$

So,

$L_1=\{a,a^2,a^4,a^8,a^{16},\ldots\}$

This is not regular because the gap between consecutive string lengths keeps increasing.

So, $L_1$ is not regular.

For $L_2$:

$L_2=\{a^{2z}\mid z\ge 0\}$

The possible lengths are:

$0,2,4,6,8,\ldots$

So,

$L_2=\{\lambda,a^2,a^4,a^6,\ldots\}$

This language contains all strings of even length over alphabet $\{a\}$.

It can be written as:

$L_2=(aa)^*$

Since $(aa)^*$ is a regular expression, $L_2$ is regular.

For $L_3$:

$L_3=\{\omega\omega\mid \omega\in\{a,b\}^*\}$

In this language, the second half of the string must be exactly the same as the first half.

A finite automaton cannot remember the complete first half and compare it with the second half.

So, $L_3$ is not regular.

Therefore, only $L_2$ is regular.


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...