601 views

Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$.

1. $B$ can be recognized by a deterministic finite state automaton.
2. $B$ can be recognized by a non-deterministic finite state automaton but not by a deterministic finite state automaton.
3. $B$ can be recognized by a deterministic push-down automaton but not by a non-deterministic finite state automaton.
4. $B$ can be recognized by a non-deterministic push-down automaton but not by a deterministic push-down automaton.
5. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.
| 601 views

The given language is the intersection of two regular languages.

1. Binary strings beginning with $1$
2. Binary strings divisible by $7$ (For any integer $n,$ divisibility by $n$ for a binary string can be checked using a finite automata making the language regular.)

Intersection of two regular language is regular (Regular set being closed under intersection).

by Boss (12.4k points)
selected by
0

@Ahwan for that we need to first show that Binary string divisible by 7 is regular which is the main task.

If one can find out that binary string divisible by 7 is regular it is not tough to visualize that in initial sate if we get 0 as input we simply go to trap state and reject all strings in trap state.

+2
@Shivesh

Actually for Decimal of Binary string divisible by n is regular always,using n states it can be done always. (Its a well known problem,asked many times in gate for different values of n maybe) .

If it start with $1$ it goes to final state.

If start with $0$ it will go to the reject state.

by Veteran (119k points)
edited
+1
What should be the general approach to solve these kind of questions? I understood the DFA but am not able to understand how to approach the question.
0

@srestha is there any shortcut without drawing this humongous DFA and verifying it that whether it accepts all binary string Binary string divisible by 7 as well as rejecting those strings which are not divisible by 7.

Can visualize some pattern (Regular Expression) by generating few binary strings which start with 1 and divisible by 7.

0

@Chandrashis Mazumdar

It is simple, you only need to think whether you can make a DFA for it or not.

It is important to to know that

(i) We are not dividing the number with 7 but we are observing if the number is divisible by 7.

For part (i):

So,we can see for divisibility by 7 by counting the remainders as

(1) Remainder 0

(1) Remainder 1

(2) Remainder 2

(3) Remainder 3

(4) Remainder 4

(5) Remainder 5

(6) Remainder 6

So, 7 states are sufficient to check divisibility by 7.So, its regular.

Part (ii)

Its regular because its starts with 1.And for 0 we reject it.

Thus , part (i) and part (ii) both are regular.And due to closure property the entire statement is regular.Option A is correct
by Active (3.6k points)