Question

Let $L_1=\{wϵ{\{0,1\}}^{\ast }\mid whasatleastasmanyoccurrencesof(110{)}^{\prime }sas\left(011{)}^{\prime }s\right\}$. Let

$L_2=\{wϵ{\{0,1\}}^{\ast }\mid whasatleastasmanyoccurrencesof(000{)}^{\prime }sas\left(111{)}^{\prime }s\right\}$ Which one of the Following is TRUE?

• A. $L_1$ is regular but not $L_2$
• B. Both $L_1$ and $L_2$ are regular
• C. $L_2$ is Regular but not $L_1$
• D. Neither $L_1$ nor $L_2$ are regular

Answer 1

The correct option is A $L_1$ is regular but not $L_2$

A machine which accepts $L_1$ needs only finite memory since there is no need to keep the number of 110's in memory. The reason is because whenever two consecutive 110's come in a row then a 011 always come in between as shown below.

110110

So the difference between number of 110 and number of 011 can only be 1, 0,-1.

So only finite memory needed and therefore $L_1$ is regular.

$L_2$ requires infinite memory since any number of 000's can come in a row without any 111 in between. So the difference between the number of 000's and 111's can go upto $\infty$ or- $\infty$.So this language requires inifinite memory. But FA has only finite memory.

So $L_2$ is not regular.