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?

Open in App

Solution

Choise (a) is regular since it is finite.

Choise (b) is regular since although comparision is made between 0's and 1's, it is for all prefixes and this can be done by DFA.

Note: $∣ n_{0} (s^{'}) - n_{1} (s^{'}) ∣\leq 2 i s s a m e a s n_{0} (s^{'}) - n_{1} (s^{'}) \geq 2 o r n_{1} (s^{'}) - n_{0} (s^{'}) \geq 2.$

Choice (c) involves comparision of number of 0's and 1's but for the string as a whole, and this cannot be done by a dfa, since it has finite memory and has no stack for counting upto infinity. Therefore, choice (c) is not regular.

Choice (d) is regular since $n_{0} (s) m o d 7 = n_{1} (s) m o d 5 = 0$ means number of 0's is divisible by 7 and number of 1's is divisible by 5 and this can be accepted by a dfa with 7 $\times$ 5 = 35 states.

A minimal DFA that will accept the language of choice (b) is shown below:

Suggest Corrections

Similar questions

Let |L|: denotes the number of strings present in L.

Let R and S be two languages,

such that | R \cup S | = 96 a n d | R \cap S | = 32.

T h e n | (R - S) \cup (S - R) | is equal to________.

Which of the following regular expressions describes the language over {0, 1}

consisting of string that contain exactly two 1's ?

For S ∈ (0+1)* let d(S) denotes the decimal value of S (e.g., d(101) = 5).
Let L = S ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 ≠ 4
Which one of the following statements is true?

Q. Let r =1

(1 + 0)^{*}, s = 11^{*} 0 a n d t = 1^{*} 0

be three regular expressions. which one of the following is true?

Q. The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively

Join BYJU'S Learning Program

If s is a string over (0+1)∗, then let n0(s) denote the number of 0's in s and n1(s) the number of 1's in s. Which one of the following languages is not regular?

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?