edited by
503 views
2 votes
2 votes

Which of the following sets can be recognized by a Deterministic Finite State Automation?

  1. The numbers $2^0, \ 2^1$ to $2^n$ written in unary.
  2. The numbers $2^0, \ 2^1$ to $2^n$ written in binary.
  3. The set of binary strings where the number of zeros is the same as the number of ones.
  4. The set $\{1,101,11011,1110111, \dots \}$
edited by

1 Answer

0 votes
0 votes

In decimal (base 10), how do we know a number is divisible by 10? We check if it ends with a 0.

30, 50, 6670 etc.

 

How do we know a number is divisible by 100? (square of base) We check if it ends with two 0's.

300, 757600, 1500 etc.

 

So, in binary (base 2) how do we check if a number is divisible by 2? It must end with a 0.

 

To be divisible by 4 (square of base) it must end with two 0's. And so on.

 

Hence, the language $2^0,2^1,2^2,2^3,2^4,2^5...$

which is equivalent to $1,2,4,8,16,32...$ in decimal

which is equivalent to $1,10,100,1000,10000...$ in binary

is actually just the regular expression $10^*$

 

So, Option B is correct.


If written in unary, then that is counting. FAs don't have memory. They can't count.

Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,184 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
297 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
205 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4