The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 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
asked in Theory of Computation by Active (3.7k points)
edited by | 1.2k views
@Arjun Sir please solve this too ...
@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 ...
How the first part is regular?
so Sir you are saying that first and second part is not regular ?

Sir here is the DFA for the first part

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

1 Answer

+36 votes
Best answer

Refer this:

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

answered by Veteran (55k points)
edited by
Sir, L1 ∩ L2  will have 5*7 = 35 states out of which 6 will be final right ?

@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?

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

Thank you, Sir!

 Praveen Saini sir

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

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,058 questions
45,554 answers
48,920 users