GATE CSE 2006 | Question: 30

Question

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?

• A. $L$ is recursively enumerable, but not recursive
• B. $L$ is recursive, but not context-free
• C. $L$ is context-free, but not regular
• D. $L$ is regular

Comments

Sir i think that similarly we can draw a DFA for mod 7 ... in that DFA all the states Except "mod4" state will be a final state.

---

complete banao, tab maane ..;)

---

For mod-5,we can define a machine as follows:

M = {(0,1,2,3,4), (0,1), (0), $\delta$, (2)}, where we read the string bit-wise and $$\delta(q, x) = (2q + x) \text{ mod } 5$$.

For mod-7, we can define a similar machine as follows:

M = {(0,1,2,3,4,5,6), (0,1), (0), $\delta$, (0,1,2,3,5,6)}, where we read the string bit-wise and $$\delta(q, x) = (2q + x) \text{ mod } 7$$.

Post this, we only need to take the product of this automata and we'll get the desired answer.

Here, we'll have 35 states, out of which 6 will be final ( which is obtained by the product of the respective final states.)

Answer 1

$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

Comments

@Praveen Saini

@Deepak Poonia sir here if instead of and ,given ”or” , then number of final states will be 31 bcz f24, is also a final state bcz d(s) mod 5=2.

We can do this way also 7+30-6 = 31.

---

@samarpita It would be $31$

Total states = $7*5 = 35$

Non-final states = $(x0y4, x1y4,x3y4,x4y4) = 4$

The final states for ‘OR’ :- $Total – non final = 35-4 = 31$

---

@Abhrajyoti00 yes i have corrected..it will be 31.

Answer 2

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 3

the DFa for second part 1st part is already available