The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+36 votes

If $s$ is a string over $(0+1)^*$  then let $n_0(s)$ denote the number of $0$’s in $s$ and $n_1(s)$ the number of $1$’s in $s$. Which one of the following languages is not regular?

  1. $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit  prime } \right \}$
  2. $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$
  3. $L=\left \{ s\in (0+1)^*\mid n_{0}(s)-n_{1}(s)\mid \leq 4 \right \}$
  4. $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$
asked in Theory of Computation by Active (3.3k points)
edited by | 5.1k views
I will explain only option B because rest are clear. so option B says EVERY prefix of S follow the rule of |0's - 1's| <=2

people like me who are thinking strings like this 00011 should have accepted but because of "every prefix" word there is more prefix to this prefix also which is 000 and which will not be accepted since we will start to analyse prefixes from lower length to higher length and if any one substring is not accepted we stop and say This string do not follow the rule. So this is regular.
Can you please explain why we are considering option b as regular. To know the difference we will have to count the number of zeros and one's but if we do that , it means it is not regular

6 Answers

+32 votes
Best answer

A. There are only finite $3$ digit primes. Let the largest of them be $X$. Now we need $X+2$ states in our DFA (including one for $count =0$ and one for $count > X$).  We do not need a change of state for any $1$.

B. Here we need just $6$ states to recognise $L$. 

  1. $\#0 - \#1 = 0$
  2. $\#0 - \#1 = 1$
  3. $\#0 - \#1 = 2$
  4. $\#0 - \#1 = -1$
  5. $\#0 - \#1 = -2$

If the difference goes above $2$ or below $-2$, we go to a dead state. All other states are accepting. This transition to dead state is possible because of the words "for every prefix $s'$ of $s$" in $L$ and that is what makes this language regular. 

C. $L$ is not regular

$\#0 - \#1 = 1$
$\#0 - \#1 = 2$
$\#0 - \#1 = 3$
$\#0 - \#1 = 4$
$\#0 - \#1 = 5$
$\#0 - \#1 = 1000$

All these form distinct equivalent classes under Myhill-Nerode theorem meaning from the strings in each of these sets, we can append a string which will take the new string to $L$, while the same string appended to string in any other set would not reach $L$. 

For example, for $000000$, we append $11$, for $0000000$, we append $111$ etc. So, in short we need to maintain the count of $1's$ and $0's$ and the count here is not finite. 

D. This is regular. We need a finite automata with $5 \times 7 = 35$ states for maintaining the counts of $0's \mod 7$ and $1's \mod 5$ and there cannot be more than $35$ possibilities for this. With each input symbol, the transition must be going to one among these. 

Correct Answer: $C$

answered by Veteran (414k points)
edited by
Please explain option D sir....How do we know that it will take 35 states?
mod 7 - 7 possibilities. mod 5 - 5 possibilities. So, totally 35 possibilities. With each input symbol, the transition must be going to one of these 35 states.
Nopes, because at some point of the input string the difference can be say 10 and in the end it can come to say 1. That is why we need "every prefix" condition to make it regular. Consider the string "0000000000111111111"
why are we going from -2 to 2 only?I am not able to understand this concept
because the B option in question says so- no. of 1's and 0's till any part of string can differ by up to 2 only.
yeah rt thanx.Is prefix same as substring but with length less than string?
Prefix is a substring but must have the same start as the string.
thank you.Plz could you answer this question of mine.I really need help on this
Prefix of (a+b) * is (a+b)*. So what make it special.. Is it seems Like option c.. Clear my doubt

@Arjun Sir, I have few doubts.

(1) Would the language in option (b)  would have been regular if "for every prefix s' of s" words were not there?

(2)If we modify the language in option (b) as

L={s∈ (0+1)* | for every prefix s' of s | n0(s)-n0(s')<=2 }

will this language be regular?


1. No

2. Yes regular . Lang=all strings having atmost 2 zeros


Thats not the language what ayush mentioned in his question 2 .

Say string s -00011 and its prefix s' 00 

3-2= 1 satisfying the language

 L={s∈ (0+1)* | for every prefix s'of s | n0(s)-n0(s')<=2 }


@Ayush Upadhyaya

Please correct if wrong

L={s∈ (0+1)* | for every prefix s' of s | n0(s)-n0(s')<=2 }

will this language be regular?

Yes ...n0(s) <= n0(s') + 2..

For first prefix epsilon we just check n0(s) < = 0 + 2

no(s) <= 2..after that it can be no(s) <= 3  no(s) <= 4.....

hence strings containing atmost 2 zeros..

If it is n0(s') - n0(s) <= 2..then it will be non regular right ???

+106 votes

A. $n_0(s)$ is a $3$ digit prime. It means no. of $0's$ are in the range (set) $\{101,103,\ldots,997\}$ which is finite. So, $L$ will be regular. 
For simplicity consider $n_0(s)$ is a $1$ digit prime. So set will be $\{\}.$ DFA will look like

B. Prefix - For a string $s,$ its prefix $s'$ is any substring from the beginning of $s.$
Example: $s = 10110, s' = \{1, 10, 101, 1011, 10110\}.$

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$

So, here we have to ensure that no where in our string the difference between number of $0's$ and $1's$ is greater than $2.$ If anywhere the above condition fails, we will enter a dead state as we got a substring (prefix) that violates the condition.

DFA will be like

So, here the difference between number of $0's$ and $1's$ crosses $2$ we will be in dead state.
e.g., $s=10110, s' = \{1, 10,101,1011,10110\}$
This string will be accepted as nowhere in $s'$ the difference exceeds $2$.
$s=011110, s'=\{0,01,011,0111,\underbrace{01111}_{\text{diff} = 3},011110\}$
This string is not accepted.

C. The difference between the number of $0's$ and $1's$ should not exceed $4.$
Here, once we exceed the limit there is a possibility that we might cover up the difference in further part of the string.
e.g., $0111111000$
Here, just by seeing up to the last $1$ we cannot move to dead state. So, it needs infinite counting. Hence, not regular.

D. This language can be stated as the set of strings where number of $0's$ is divisible by $7$ and number of $1's$ is divisible by $5.$ We can make a DFA for this by cross-product method. Hence, regular. 

answered by Active (1.2k points)
edited by
Nice Ans.
It should be best solution.
Good answer !
The prefix of a language should also contain $\epsilon$
If this handwriting is bad, then I am a martian.
In  option b dfa reject the string111000

#0-#1=0 which is in the range.
Can I say to balance nos of one's and zero's we may end up infinite counting hence it is not regular language ?
How it can be in range ?
if we take 111 then #0-#1 is not in range hence rejected.
In your  dfa  0001 is not accepting. ........

Help me out
Here also  3zeros -1 ones=2
See it step by step, one symbol(digit) at a time. Since we have to preserve this property for each and every sub-string of the given string.

Your string is 0001. For first 0(which is also a substring of 0001) the property |#0 - #1| ≤ 2 holds. Now take the next 0, so for 00(the next substring) again this property holds. Now if we include the third 0, the substring will be 000. But here the property |#0 - #1| ≤ 2 doesn't hold. So this substring is not satisfying the given condition. Hence, the string( here 0001) of which 000 is a substring is not accepted. We need not see the later symbols if the property is not maintained for any substring.

Hope this clears your doubt.
best explanation
Is there any method to know the exact number of states in such questions as in option b......
+4 votes

option C includes 0n1n which is DCFL.

Answer C

answered by Boss (13.4k points)
"includes" is a wrong word. You can say the problems (problem of accepting those kind of words) are similar.
When I was writing this I know I was wrong, but I am not able to come up with correct phrase. thanks for correcting.
Will u explain y second option (b) would b regular and y option (c) is not regular.

finding every prefix of regular language  is not possible so it should not b regular

and in (c) inspite it contain some a^nb^n but are bounded,,so option (c) should b regular
B is regular and C is not. I have explained in the answer.
+1 vote
Option c

3 digit prime num-finite

Prefix closed under regular

Option d too regulr
answered by (437 points)
0 votes
C is not all are regular
answered by Boss (30.7k points)
can u elaborate why?
a) is regular because finite nos of 3 digit primes are there..

b) is regular because it will be like 0+1+(01)*+(10)*+00(01)*+11(01)*+0011(01)* i am not writimg complete terms but i want to show that only finite nos of regular expression terms are neede to represent it so, it is regular..

d) is regular, this one is very trivial..35 states are needed.

c) now this is not regular, you can decompose above language into union of 4 languages having,


consider |n0(s)-n1(s)|=1...strings in this language can be 001, 100, 00000000000011111111111..there can be 10 millions consecutive 0's followed by10 millions-1 consecutive 1's...or there could be 100 0's followed by 99 1's...therefore you can not check it by finite no of states...and count of 0's are needed to find count of 1's and vice not is NCFL..
for option D if restricted on like no of a's is divisible by 3 and 5 then how many states possible minimum ?
if i have to know what is the exact number of states in dfa of option can i do it sir...
–1 vote
opt a)  3digit prime it is finite(101,103.....997).so it is regular

opt b) we cant construct dfa for |no.of a's-an.of b's|<=2. for each prefix.

opt c)we can contruct dfa for more no.of 1's than 0's   like that possible to construct |no.of a's-no.of b's|<=4 so,it is regular

opt d) already we know that regular.

so ans is: opt B
answered by (63 points)
Answer is C, you can construct DFA for B, but not C it is DCFL.
Here problem is only in Option B and C both are looking non - regular but option B is regular and option C is non-regular.

first understand meaning of every prefix word in problem.. e.g. prefix means first n symbol. i.e. substring here 100011111 -> while scanning from 1) 1 -> difference is 0  2) 3 0's -> difference  is 2 3)  5 1's -> difference become 3 and now string will never be accepted whatever will be there after that. that is why prefix  of every string is always finite.


but for option C they are saying to scan whole string which is infinite so that difference will vary from greater than four i.e may be 4+ and again while reading next input difference will again reduced to four or less than four. which in turn infinite so that option C is non-regular

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
49,814 questions
54,516 answers
75,286 users