1.6k views

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 | 1.6k views
0
@Arjun Sir please solve this too ...
+1
@Arjun Sir solution which I have says (B) but I think it is (D) as Regular languages are closed under intersection . Can We apply closure property here ? please reply ...
0
How the first part is regular?
0
so Sir you are saying that first and second part is not regular ?
0
yes.
+6

Sir here is the DFA for the first part

0
:) For the second part?
+3
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.

Refer this:

https://gateoverflow.in/1695/gate1998_4

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

edited
+3
Sir, L1 ∩ L2  will have 5*7 = 35 states out of which 6 will be final right ?
+1
right.
0

@Praveen Saini Sir, wouldn't the total final states will be 7?

6 from mod 7 counter and 1 from mod 5 counter.

Edit: I guess we will consider state 2 only once as it's common in both?

+9
in intersection final state will be that where we get final of first and second dfa together.

$(x_2,y_0),(x_2,y_1),(x_2,y_2),(x_2,y_3),(x_2,y_5),(x_2,y_6).$
0
Thank you, Sir!
0

if or instead of and in the question still there will be 6 final states

+4
7*5 - 1*4 = 31 (all states - nonfinals)
0
isn't it called cross product...?
0
Yes. It is
0

@just_bhavana & @Praveen Saini,

while finding the number of states when we do multiplication and when we take lcm ..??

0

any ques in which lcm is taken pls share ,bcoz I am unable to any such thing

1
2