The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
305 views
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 :)
asked in Theory of Computation by Loyal (2.9k points)
retagged by | 305 views

2 Answers

+1 vote
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.
answered by Veteran (13.4k points)
For all i , where i belongs to natural numbers.
0 votes
try to write its corresponding regular expression .

regular expression for this language is-0((11)*(000+00)*)*
answered by Active (2.2k points)
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 .


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,167 questions
36,992 answers
92,219 comments
34,837 users