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

+36 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.4k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,058 questions

45,554 answers

131,902 comments

48,920 users