The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
1k 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
asked in Theory of Computation by Loyal (4.3k points)
edited ago by | 1k 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 ?
yes.

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

+34 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.

answered by Veteran (55.2k points)
edited ago by
Sir, L1 ∩ L2  will have 5*7 = 35 states out of which 6 will be final right ?
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.

$(x_2,y_0),(x_2,y_1),(x_2,y_2),(x_2,y_3),(x_2,y_5),(x_2,y_6).$
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

33,687 questions
40,230 answers
114,268 comments
38,793 users