Is this language regular?

Question

Is L={0, 011, 011000, 0110001111, ....} a regular language?

I know that the language should follow some regular pattern and we should be able to construct a regex for it in order to say it a RL. Morever it shouldnt require any kind of extra memory to store the counts.

BUT, in this given language, I can see a regular pattern, but I am not able to construct a regex. And I think that prevois count should be remembered by the m/c.. So it should be NRL. But my book says its a RL. I am not getting how??

 

P.S. I wud be thankful if somebody suggests a quick method to identify given set to be RL or NRL based on pattern.

Thanks in advance :)

Answer 1

try to write its corresponding regular expression .

regular expression for this language is-0((11)*(000+00)*)*

Comments

But the next string in given set will be 011000111100000. Which the given RE is not generating.

Ohkay! Got it! Will write it for odd 0s. Thanx bro :)

---

how is this regular. how 5 zeros will be generated

---

WITH THIS EXPRESSION 0110000 OR 000 STRING IS ACCEPTED AND MANY OTHER .

THIS LANGUAGE IS`NT REGULAR .

Answer 2

Did NOT looks like a regular language. Instead of analysing the exact pattern and positions of 1's and 0's in the strings of the language, try to count the number of 0's and 1's. You will notice that, if the number of 0's in any string of this language is i^2, then the number of 1's have to be either (i^2 + i) or (i^2 - i). I don't think that this dependency can be preserved by any regular language. Even it does not seems like a Context Free Language to me.

Comments

For all i , where i belongs to natural numbers.