The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $L$ is recursively enumerable, but not recursive
- $L$ is recursive, but not context-free
- $L$ is context-free, but not regular
- $L$ is regular

+35 votes

Best answer

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.

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 449
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,499 questions

42,768 answers

121,499 comments

42,151 users