The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
353 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 Active (2.7k points)
retagged by | 353 views

2 Answers

+1 vote
try to write its corresponding regular expression .

regular expression for this language is-0((11)*(000+00)*)*
answered by Active (2.3k points)
0
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 :)
0
how is this regular. how 5 zeros will be generated
+1
WITH THIS EXPRESSION 0110000 OR 000 STRING IS ACCEPTED AND MANY OTHER .

THIS LANGUAGE IS`NT REGULAR .
+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 Boss (13.8k points)
0
For all i , where i belongs to natural numbers.

Related questions



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

44,076 questions
49,595 answers
162,959 comments
65,791 users