The Gateway to Computer Science Excellence
+10 votes

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.
in Theory of Computation by Boss (30.8k points) | 601 views

3 Answers

+14 votes
Best answer

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).
Correct Answer: A.

by Boss (12.4k points)
selected by

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


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) .
+16 votes

Answer will be (A).

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

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


@Chandrashis Mazumdar

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

0 votes
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.

(ii) It should start with 1.

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)

Related questions

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
50,737 questions
57,355 answers
105,249 users