The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+6 votes

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

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

+11 votes

Best answer

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

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

Now, **in**** L ^{*} **if we can

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

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

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.

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 ?

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 ?

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,156 questions

36,980 answers

92,146 comments

34,822 users