2k views

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\}$

edited | 2k views
+4
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

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
edited
0
Why not d is right
+2
language given in option d is cfl
+1
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?
+1

+1
language in option B is as $L=\{a^{2^n} : n\geq 0\}$
0
how to check if language id cfl based on string given?
0
based on language given, and check whether it is accepted by pda.
0
@Praveen Saini Sir What type of language B is?
0
should be recursive.
0
Thank You Sir
0
Praveen Sir, Can we say language of option A is 0^*10^* instead of 10^* and   option B is CSL ?
0
@Saurav Basu 0*10* will get rejected as it goes to trap state on reading preceding 0's.
0
@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*
0
Is there a correction here? The correct answer is option A, right?
0
0

Praveen Saini sir pls correct answer

0
did correction
0
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!!
0
can i say language b is CSL?
+1
@gurdeep b is csl

A)   as 1 in binary is 1

2 = 10

4= 100

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