The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+28 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 (59.6k points)
edited by | 2k 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

2 Answers

+40 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 (55k points)
edited by
Why not d is right
language given in option d is cfl
Doubt:How is equal number of 1s and 0s CFL? If we start with 'if zero then add 0, if one then pop out a 0 from stack'. What if we get 110100?
How will the stack know if more 0s are there in the 1st half or more 1s?

Why B option is not regular language??? Please reply.

language in option B is as $L=\{a^{2^n} : n\geq 0\}$
how to check if language id cfl based on string given?
based on language given, and check whether it is accepted by pda.
@Praveen Saini Sir What type of language B is?
should be recursive.
Thank You Sir
Praveen Sir, Can we say language of option A is 0^*10^* instead of 10^* and   option B is CSL ?
@Saurav Basu 0*10* will get rejected as it goes to trap state on reading preceding 0's.
@meghna yes you are correct , but I mean to say that language of  "The numbers 1,2,4,8,…2^n written in binary" can be 0*10* too and of course we can have a dfa for 0*10*
Is there a correction here? The correct answer is option A, right?
yes A is the answer.

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
+4 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 (105 points)

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

41,079 questions
47,675 answers
62,393 users