2.9k 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 | 2.9k views
+5
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
0
If nothing is mentioned Plz tell By default Binary strings are evaluated LSB to MSB or MSB to LSB....

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

Praveen Saini sir pls correct answer

0
did correction
+1
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
+2

this is the correct DFA for option (A).

0

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

+1

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.

+1

@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.

0
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.

A)   as 1 in binary is 1

2 = 10

4= 100

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

1
2