edited by
19,325 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

0 votes
0 votes
C is not regular...rest all are regular
0 votes
0 votes
a) is regular

b) is regular

c) not regular but DCFL

d) is regular

we can construct a finite automata for (a),(b) and (d) but not for (c).
–1 votes
–1 votes
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
Answer:

Related questions

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