The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+31 votes

Which of the following set can be recognized by a Deterministic Finite state Automaton?

  1. The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binary

  2. The numbers $1, 2, 4, 8,\dots 2^n, \dots$  written in unary

  3. The set of binary string in which the number of zeros is the same as the number of ones.

  4. The set $\{1, 101, 11011, 1110111, \dots\}$

asked in Theory of Computation by Veteran (52k points)
edited by | 2.9k views
if language is infinite and if their is no pattern exist then surely not regular . but if patten is exist then may or may not be regular and to ensure for regular if we able to draw dfa then surely it will be regular otherwise not regular
If nothing is mentioned Plz tell By default Binary strings are evaluated LSB to MSB or MSB to LSB....

2 Answers

+45 votes
Best answer

Option A is correct .

  1. A. is regular 
    $L = \{1, 10, 100, 1000, 10000, \dots \}$ 
    regular expression $10^*$
    $DFA$ :
  2. $L=\{1,11,1111,11111111, \dots \}= \{1^i \mid i =2^n, n \geq 0 \}$ is non regular language
  3. Equal- Equal, is CFL, and non regular 
  4. $L=\{1^i01^i   \mid i>0\}\cup \{1\}$ is also CFL, and non regular 
answered by Veteran (55.8k points)
edited by

Praveen Saini sir pls correct answer

did correction
I understood why A is correct, but why not B?

We can have dfa for 1* where starting state is acceptable state with transition to same state depending on nos of 1 for a given number in unary. Please help!!
can i say language b is CSL?
@gurdeep b is csl

this is the correct DFA for option (A).


@Praveen Saini sir,  Why not R.E for Option A is  $0^*10^*$  ?
Strings like 00100 etc should be in the language.


 according to that there are infinite number of representation of 1 in binary. Any number of leading zero's are ignored and first 1 from the left is considered MSB. 0*10* and 10* result in distinct DFA's but meaning is same. Both are correct.


@Mk Utkarsh, language is a set, we have to consider all possible representations of 1.
Otherwise, 0001 is a valid string but it won't be accepted by the DFA. 

according to me there is bijection between representation on binary numbers and decimal numbers.

so 10* is appropriate answer. 0*10* sahi hone ke liye you have to prove 1 has infinite representation in binary.
+5 votes

A)   as 1 in binary is 1

            2 = 10

            4= 100

and so on so language is  10*  so DFA can be formed.

answered by (99 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
49,540 questions
54,099 answers
71,007 users