The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+35 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?

- $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime } \right \}$
- $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 \}$
- $L=\left \{ s\in (0+1)^*\mid n_{0}(s)-n_{1}(s)\mid \leq 4 \right \}$
- $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$

+28 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$.

- $\#0 - \#1 = 0$
- $\#0 - \#1 = 1$
- $\#0 - \#1 = 2$
- $\#0 - \#1 = -1$
- $\#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$

$\vdots$

$\#0 - \#1 = 1000$

$\vdots$

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.

+2

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.

+1

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"

0

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.

+1

thank you.Plz could you answer this question of mine.I really need help on this

https://gateoverflow.in/43519/refrence-books-for-gate#a43523

https://gateoverflow.in/43519/refrence-books-for-gate#a43523

0

@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 | n_{0}(s)-n_{0}(s^{'})<=2 }**

will this language be regular?

+77 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 $\{2.3.5.7\}.$ 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.

0

Can I say to balance nos of one's and zero's we may end up infinite counting hence it is not regular language ?

0

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.

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.

+4 votes

+3

"includes" is a wrong word. You can say the problems (problem of accepting those kind of words) are similar.

+1

When I was writing this I know I was wrong, but I am not able to come up with correct phrase. thanks for correcting.

–1 vote

opt a) 3digit prime num.so 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

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

+4

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

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

–1 vote

0

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)*...now 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,

|n0(s)-n1(s)|={0,1,2,3,4}...now,

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 versa...so not regular...it is NCFL..

b) is regular because it will be like 0+1+(01)*+(10)*+00(01)*+11(01)*+0011(01)*...now 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,

|n0(s)-n1(s)|={0,1,2,3,4}...now,

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 versa...so not regular...it is NCFL..

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,558 answers

146,288 comments

62,305 users