edited by
19,327 views
83 votes
83 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 \}$
edited by

8 Answers

Best answer
71 votes
71 votes

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$
$\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. 

Correct Answer: $C$

edited by
242 votes
242 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. 

edited by
8 votes
8 votes

option C includes 0n1n which is DCFL.

Answer C

5 votes
5 votes

I'll just try to eliminate the confusion why B is RL, but C is not.

In B, "every prefix" should be such that n0 − n1 ≤ 2.
How do we check for every prefix? Just remember this fact that regularity is closed under prefixes.
If length of s = 5, length of all its prefixes would be ≤ 5.
We'll only accept the language such that at each step, the given condition is satisfied.
At length = 1, length = 2... so on, if we don't let the given condition violate, eventually our final string won't have any smaller / "earlier" components (prefixes, loosely) that violate the given condition. So we actually can do this with FAs.

 

Now look at C. n0 − n1 ≤ 2 in the string. (NOT THE PREFIX. That's the difference in B and C)
So, if a string starts like 0111111111, we'll let it go in hopes that maybe in the end a bunch of 0's will come and settle the count. When would the end come, we don't know. Maybe the string is infinite. Hence, it needs to keep track of the count till infinity, hence can't be done with FA.
Can be done with PDA.

 

Hence, B is RL, and C is not RL.

Just for the sake of completion, A is finite, and D has a pattern. So, both RL.

Answer:

Related questions

93 votes
93 votes
8 answers
1
Rucha Shelke asked Sep 22, 2014
33,978 views
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$