1,940 views
15 votes
15 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.

3 Answers

Best answer
19 votes
19 votes

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.

selected by
18 votes
18 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.

edited by
0 votes
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
Answer:

Related questions

18 votes
18 votes
4 answers
2
makhdoom ghaya asked Dec 7, 2015
2,322 views
Let $a, b, c$ be regular expressions. Which of the following identities is correct?$(a + b)^{*} = a^{*}b^{*}$$a(b + c) = ab + c$$(a + b)^{*} = a^{*} + b^{*}$$(ab + a)^{*}...
20 votes
20 votes
5 answers
4