TOC Regular Langauges

Question

Is L= 0ⁿ1| n>=0 regular?

Is the kleene closure i.e. (L)^* regular?

 

Comments

Kleene Closure property holds under Regular Language.

---

Verma Ashish

I guess if n every time is same then it can't be  regular but if its independent then yes its regular.

I mean

if (0ⁿ1)³=(0^m1)(0ⁿ1)(0^o1) where the powers of 0 m,and o need not be equal, then its regular

else if

(0ⁿ1)³=(0ⁿ1)(0ⁿ1)(0ⁿ1) Here all the powers are same and cannot be regular

And Kleene closure of regular language is regular so I guess (0ⁿ1)³  expansion is the first one. But again I am not sure.

Also I think (0ⁿ1)|n>=0 is same as (0*1) [Correct me if I am wrong] and when kleene closure is applied, the powers dont have to be same so we can say its regular.

---

Why all of you making the simple question so Difficult ???

Just check there is a comparison or unbounded waiting then it will not be Regular.

Answer 1

Given a set V define

$V_0 = \left \{ \epsilon \right \}$ (the language consisting only of the empty string),

$V_1 = V$

and define recursively the set

$V_{i+1} =    \left \{ wv : w ∈ V_i  \ \text{and} \ v \in V \right \} \text{for each i>0.} $

If V is a formal language, then V_i, the i-th power of the set V, is a shorthand for the concatenation of set V with itself i times.

The definition of Kleene star on V is 

$V^* = \bigcup\limits_{i\geq 0}^{} V_i = {\epsilon} \ \cup \ V_1 \ \cup V_2 \ \cup \ V_3 \ \cup .....$

Now coming to language provided in question,

$L = \{ 0^n 1, \ n \geq 0  \}$

$L^* = \{ 0^n 1, \ n \geq 0  \}^* $

$L_0 = \{ \epsilon \}$

$L_1 = L = \{ 0^n 1, \ n \geq 0  \}$

$L_2 = \{ wv : w \in V \  \text{and}  \ v \in V \}$ = $\{11, 101, 0101, ....  \}$

and so on for $L_3 , L_4 ,....$

$L^* = \bigcup\limits_{i\geq 0}^{} L_i = {\epsilon} \ \cup \ L_1 \ \cup L_2 \ \cup \ L_3 \ \cup .....$

this can also be written as $(0^*1)^*$ and it generates a regular language.

 

 

 

Answer 2

It's Regular Because There is no comparison and Unbounded waiting.

Most Important point check a language is regular or not is 

 1. There should not be Unbounded waiting and comparison.

2. If Language is not in AP then it will not be a Regular Language.