378 views

Which one of the following languages over the alphabet ${0, 1}$ is regular?

1. The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively.
2. The language of palindromes, i.e. bit strings $x$ that read the same from left to right as well as right to left.
3. $L= \left \{ 0^{m^{2}}: 3 \leq m \right \}$
4. The Kleene closure $L^*$, where $L$ is the language in $(c)$ above.
5. $\left \{ 0^{m} 1^{n} | 1 \leq m \leq n\right \}$
edited | 378 views

Here , OPTION D is regular, reason is as follows :

L = { 0^ m2  : m>= 3}0m20

Now, in L* if we can generate 9 continuous powers of zero, then further every power can be generated by concatenating  09.

Here , L = {0,016, 025 , ...}

So, here are 9 continuous powers:

0120 : 016 016 016 09 09 09 09 09 09 09 09

0121 : 016 016 016016016016025

0122 : 016 016 09 009 09 09 09 09 09 09 09

0123 : 016 016 016 025 025 025

0124 : 016 018 018 018 018 018 018

0125 :025 025 025025 025

0126 : 018018018018018018018    {018 can be generated as 09 09 }

0127 : 016 016 016 016 09 09 09 09 09 09 09

0128 : 016 016 016 016 016 016 016 016

Now, 0129  can be given as 0120 0and so on..

Every Further powers can be generated by concatenating  09.

selected by
what is the significance of this "10" ?
ya, 9 would suffice, edited my answer :)
still answer is not clear- all powers can be generated, but more than that any higher length string is in L. So, after this length, every string is simply accepted..

all powers can be generated-  any higher length string is in L.. both sound same as there is no alphabet symbol other than 0.. that itself concluding any bigger length string can be generated

yes, I took it as "square" as in question..
How did you calculated the exact figure?Is there any trick?
how will we know the continuous powers will be from 0^120? is it just by trial n error or there is some way to get it?
–1 vote
Option A can be reduced to the language of the form 0 $^{n}$ 1 $^{n}$  as to balance parenthesis it should have equal number of 0 followed by equal no of 1. Therefore not regular.

Option C : L = { 0 $^{9}$ , 0 $^{16}$ , 0 $^{25}$ .........} This language cannot be regular because there is no specific pattern in the language .

Option D : L $^{*}$  also contains L above which is not regular and it cannot be regular.

Option E : the condition n <= m has to remembered which a FSA cannot and hence not regular.

Option B : This is the usual Context free language and hence not regular.
edited
Palindrome is a usual example for CFL. $\Sigma^*$ is regular and contains strings from even non r.e. set in it.
@Arjun sir for the option D :

L*= {0^9 , 0^16 , 0^25 , 0^34 , 0^36 , 0^41, 0^49 , 0^52 ...........} There is no pattern i can find thats why i said it non regular . Where am i going wrong ?
I was telling about your argument for option D. Is C not regular? you missed the condition..
How is C regular m >=3 ?  , there is no upper bound that will make the language finite .

@Arjun sir correct me plz
sorry.. D?
Yes it can be after some point it might generate all powers of zero but i cannot find that exact power .