edited by
4,007 views
19 votes
19 votes

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 by

3 Answers

Best answer
25 votes
25 votes

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

$L = \{ 0^ {m^2} : m \geq 3\}$

Now, in ${L^*}$ if we can generate $\bf{9}$ continuous powers of zero, then further every power can be generated by concatenating $\bf{0^9}$.

Here , ${L =\{0^9, 0^{16}, 0^{25}, ...\}}$

So, here are ${9}$ continuous powers:

${0^{120}: 0^{16}0^{16}0^{16}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}}$

${0^{121}: 0^{16}0^{16}0^{16}0^{16}0^{16}0^{16}0^{25}}$

${0^{122}: 0^{16} 0^{16}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}}$

${0^{123}: 0^{16}0^{16}0^{16}0^{25}0^{25}0^{25}}$

${0^{124}: 0^{16}0^{18}0^{18}0^{18}0^{18}0^{18}0^{18}}$

${0^{125}: 0^{25}0^{25}0^{25}0^{25}0^{25}}$

${0^{126}: 0^{18}0^{18}0^{18}0^{18}0^{18}0^{18}0^{18}}$ ${\{0^{18} \text{can be generated as} 0^{9}0^{9}\}}$

${0^{127}:0^{16}0^{16}0^{16}0^{16}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}0^{9}}$

${0^{128}:0^{16}0^{16}0^{16}0^{16}0^{16}0^{16}0^{16}0^{16}}$

Now, ${0^{129}}$  can be given as ${0^{120}0^{9}}$ and so on.

Every Further powers can be generated by concatenating ${0^{9}}$.

edited by
6 votes
6 votes
def tifrregular(a) : 
    i = 3
    while (i * i <= a) : 
        if(i*i ==a):
            print("{} = {}*{}".format(a,i,i))
            return

        j = i 

        while (j * j <= a) : 
            k = j 
            if(i*i + j*j == a):
                print("{} = {}*{} + {}*{}".format(a,i,i,j,j))
                return

            while (k * k <= a) : 
                l = k 
                if (i * i + j * j + k * k == a):
                    print("{} = {}*{} + {}*{} + {}*{}".format(a,i,i,j,j,k,k))
                    return


                while (l * l <= a) : 
  
                    if (i * i + j * j + k * k + l * l == a) :          
  
                        print ("{} = {}*{} + {}*{} +". 
                                format(a,i,i,j,j), end = " ") 
                        print ("{}*{} + {}*{}". 
                                   format(k,k,l,l), end="\n") 
                        return
                    l = l + 1
                k = k + 1
            j = j + 1
        i = i + 1


for i in range(200):
    tifrregular(i)

 

A) is not regular as it requires a stack to verify parentheses matching
B) is also not regular as we require a stack or other memory to check it’s a palindrome or not
C) Is not regular because we can not check if it a length of string is a square or not only by dfa 

E)Not a regular because we required to store value of M and Decide whether M<=N or not

no let us discuss D


My program use principle of langrage's theorem for any positive integer can be represented sum of squares of 4 integers

https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four.

I just modified code using above principle to n=>3 so all numbers can be represented by 
i created python program for this you can clearly see after 72 we get continuous length string

clean closure of single alphabet language is just addition of length of strings so let’s discuss length only

Here number represent length of string of language and addition represent concatenation

MISSING NUMBERS are LENGTH OF STRINGS THAT ARE NOT ACCEPTED BY LANGUAGE

so strings length more than 72 accepted by language that’s why it’s regular

ANS IS D


9 = 3*3
16 = 4*4
18 = 3*3 + 3*3
25 = 3*3 + 4*4
27 = 3*3 + 3*3 + 3*3
32 = 4*4 + 4*4
34 = 3*3 + 3*3 + 4*4
36 = 3*3 + 3*3 + 3*3 + 3*3
41 = 3*3 + 4*4 + 4*4
43 = 3*3 + 3*3 + 3*3 + 4*4
45 = 3*3 + 6*6
48 = 4*4 + 4*4 + 4*4
49 = 7*7
50 = 3*3 + 3*3 + 4*4 + 4*4
52 = 3*3 + 3*3 + 3*3 + 5*5
54 = 3*3 + 3*3 + 6*6
57 = 3*3 + 4*4 + 4*4 + 4*4
58 = 3*3 + 7*7
59 = 3*3 + 3*3 + 4*4 + 5*5
61 = 3*3 + 4*4 + 6*6
63 = 3*3 + 3*3 + 3*3 + 6*6
64 = 4*4 + 4*4 + 4*4 + 4*4
65 = 4*4 + 7*7
66 = 3*3 + 4*4 + 4*4 + 5*5
67 = 3*3 + 3*3 + 7*7
68 = 3*3 + 3*3 + 5*5 + 5*5
70 = 3*3 + 3*3 + 4*4 + 6*6
72 = 6*6 + 6*6
73 = 3*3 + 8*8
74 = 3*3 + 4*4 + 7*7
75 = 3*3 + 4*4 + 5*5 + 5*5
76 = 3*3 + 3*3 + 3*3 + 7*7
77 = 3*3 + 4*4 + 4*4 + 6*6
79 = 3*3 + 3*3 + 5*5 + 6*6
80 = 4*4 + 8*8
81 = 3*3 + 6*6 + 6*6
82 = 3*3 + 3*3 + 8*8
83 = 3*3 + 3*3 + 4*4 + 7*7
84 = 3*3 + 5*5 + 5*5 + 5*5
85 = 6*6 + 7*7
86 = 3*3 + 4*4 + 5*5 + 6*6
88 = 4*4 + 6*6 + 6*6
89 = 3*3 + 4*4 + 8*8
90 = 3*3 + 3*3 + 6*6 + 6*6
91 = 3*3 + 3*3 + 3*3 + 8*8
92 = 3*3 + 3*3 + 5*5 + 7*7
93 = 4*4 + 4*4 + 5*5 + 6*6
94 = 3*3 + 6*6 + 7*7
95 = 3*3 + 5*5 + 5*5 + 6*6
96 = 4*4 + 4*4 + 8*8
97 = 3*3 + 4*4 + 6*6 + 6*6

edited by
0 votes
0 votes
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.
Answer:

Related questions