edited by
7,541 views
53 votes
53 votes

For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let
$$L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$$Which one of the following statements is true?

  1. $L$ is recursively enumerable, but not recursive
  2. $L$ is recursive, but not context-free
  3. $L$ is context-free, but not regular
  4. $L$ is regular
edited by

3 Answers

Best answer
77 votes
77 votes

$L_1 = \{ s \in (0+1)^* \mid   d(s) \mod \ 5=2 \}$ is regular

Having $2$ as final state out of $\{0,1,2,3,4\}$ states

As given in example in posted link [in same DFA , final state will be $2$ instead of $0$ ]

Similarly, $L_2 = \{ s \in (0+1)^* \mid d(s) \mod \ 7 \neq 4 \}$ is also regular

Having states $\{0,1,2,3,4,5,6\}$ and all are final state except $4$

$L_1 \cap L_2$ is $L$ (given problem ) is also regular

As regular languages are closed under intersection. D is correct option.

Reference: https://gateoverflow.in/1695/gate1998_4

edited by
4 votes
4 votes

D(S) Mod 5 = 2 is Regular.
D(S) Mod 7 != 4 is Regular.

Intersection of  above 2 will also be Regular because Regular languages are closed under Intersection , Therefore Option D is valid.

 

Answer:

Related questions

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