GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
296 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 \}$
asked in Theory of Computation by Veteran (38.7k points)  
edited by | 296 views

2 Answers

+8 votes
Best answer

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.

answered by Veteran (16.2k points)  
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.
answered by Boss (7.1k points)  
edited by
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 .

Related questions



Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points


25,991 questions
33,561 answers
79,414 comments
31,029 users